Talk:Sorting algorithm: Difference between revisions

Revision as of 10:07, 11 December 2015

Revision as of 03:00, 13 December 2015

Line 435:

== standard template library stable_sort() is not always in place merge sort ==

Standard Template Library includes a stable_sort() function, but does not define how it is implemented. In the case of Microsoft's Visual Studio, stable_sort() uses temp vectors (double the memory space, not an in-place merge sort), uses insertion sort to create chunks of 32 elements, then merges chunks until chunk size equals vector size. The sort algorithms section should not include a reference to Standard Template Libaray as an example of an in place merge sort. A specific implementation of STL's stable_sort() might use an in-place merge sort, but stable_sort() is not defined that way. [[User:Rcgldr|Rcgldr]] ([[User talk:Rcgldr|talk]]) 02:06, 9 December 2011 (UTC)

The ISO C++ standard (1998 and now 2011) gives implementation constraints on how stable_sort should be implemented.

The ISO C++ standard (1998 and now 2011) givesdoes give implementation constraints on how stable_sort should be implemented.

It says "Complexity: It does at most N log2(N) (where N == last - first) comparisons; if enough extra memory is available, it is N log(N)."

It works out that 3 STL algorithms are adaptive: inplace_merge(), stable_partition(), stable_sort(). They are allowed to acquire a temporary buffer and if the memory is available, then the minimum complexity is achieved. If the memory is not available but a smaller amount is available, then the algorithm degrades gracefully in the direction of the maximum complexity.

Line 441 ⟶ 443:

For VS2010, the temporary buffer is 0.5 the size of all the elements as the well-known trick of merge-sorting 2 halves and then merging one half in the temporary buffer with the other remaining half is employed. This cuts down the overhead.

Any algorithm that meets the complexity and stability requirements of ISO C++ can be used but most STLs use a hybrid adaptive mergesort. [[User:Stephen Howe|Stephen Howe]] ([[User talk:Stephen Howe|talk]]) 22:02, 28 January 2012 (UTC)

:For VS2005, the temporary buffer is 0.5 the size of all the elements. I don't have VS2003 or VS2008. As noted VS 2010 does the same thing, and so does VS2015. The key line is the same for VS2005, VS2010, and VS2015: _Temp_iterator<_Ty> _Tempbuf((_Count + 1) / 2); . Since it was mentioned, stable_partition() does allocate a full size temporary buffer. [[User:Rcgldr|Rcgldr]] ([[User talk:Rcgldr|talk]]) 04:45, 11 December 2015 (UTC)

== Implementation code improvements for all sort algorithms ==