Talk:Sorting algorithm: Difference between revisions

Revision as of 03:04, 13 December 2015

Revision as of 08:23, 15 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 a temp vectorsvector (double1/2 the memorysize spaceof the data to be sorted), and is not an in-place merge sort),. It 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 LibarayLibrary 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) does give implementation constraints on how stable_sort should be implemented.

Line 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)

:VS2005 stable_sort allocates a temporary buffer 0.5 times the size of the data to be sorted, so does VS2010 and VS2015. I suspect all versions of VS stable_sort allocate a half size temporary buffer. stable_partition does allocate a full size temporary buffer. [[User:Rcgldr|Rcgldr]] ([[User talk:Rcgldr|talk]]) 08:23, 15 December 2015 (UTC)

== Implementation code improvements for all sort algorithms ==