|
== 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 arrayvectors / vector 1/2(double the sizememory ofspace, thenot arrayan /in-place vectormerge tosort), beuses sorted.insertion Itsort endsto upcreate with the first halfchunks of sorted32 dataelements, inthen themerges tempchunks array/vectoruntil andchunk thesize second half in the second half of the original array /equals vector and then does a final mergesize. 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]]) 1902:2506, 69 December 20152011 (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.
| 