Talk:Sorting algorithm: Difference between revisions

Revision as of 05:21, 5 December 2015

Revision as of 19:25, 6 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 vectorsarray (double/ vector 1/2 the memorysize space,of notthe anarray in-place/ mergevector sort),to usesbe insertionsorted. sortIt toends createup chunkswith the first half of 32sorted elements,data thenin mergesthe chunkstemp untilarray/vector chunkand sizethe equalssecond half in the second half of the original array / vector sizeand then does a final merge. 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]]) 0219:0625, 96 December 20112015 (UTC)

*Since my last change that mentioned that Visual Studio stable_sort() uses a temp array 1/2 size of the array to be sorted was undone, here a snippet of the actual code from < algorithm > (VS 2005 to VS 2015 is the same):

<source lang="C">

_Temp_iterator<_Ty> _Tempbuf((_Count + 1) / 2);

// ...

void _Stable_sort(_BidIt _First, _BidIt _Last, _Diff _Count,

_Temp_iterator<_Ty>& _Tempbuf, _Pr _Pred)

// ... sort each half using buffer

_Buffered_merge_sort(_First, _Mid, _Count2, _Tempbuf, _Pred);

_Buffered_merge_sort(_Mid, _Last, _Count - _Count2, _Tempbuf, _Pred);

// ...

_Buffered_merge(_First, _Mid, _Last,

_Count2, _Count - _Count2, _Tempbuf, _Pred); // merge halves

</source>

[[User:Rcgldr|Rcgldr]] ([[User talk:Rcgldr|talk]]) 19:25, 6 December 2015 (UTC)

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