STL sort implementation

[Varun Kacholia]

Hi,
I have a question regarding SGI STL sort implementation:
In case of equal elements, will they be output in the same order each
time I sort?
(I understand that it is not a stable sort, and by "same order" I mean
"same order
*each time I sort*"). Or is there a random number used in the splitter
for qsort?

Thanks

[Kai-Uwe Bux]

Re: STL sort implementation

Varun Kacholia wrote:
[color=blue]
> Hi,
> I have a question regarding SGI STL sort implementation:
> In case of equal elements, will they be output in the same order each
> time I sort?
> (I understand that it is not a stable sort, and by "same order" I mean
> "same order
> *each time I sort*"). Or is there a random number used in the splitter
> for qsort?[/color]

(a) The SGI implementation is open for you to inspect. If I recall
correctly, it uses median of first, middle, and last entry and no random
selection takes place.

(b) An implementation is not required to use quick sort in std::sort(). In
fact, I think the SGI implementation uses introsort, a quick sort variation
with N log(N) worst case.

(c) Whether std::sort() produces deterministic outcomes for equal keys, is
up to the implementation. If you need that gaurantee, your options include:
(a) coding for a specific implementation for which you know what happens,
or (b) using std::stable_sor t().


Best

Kai-Uwe Bux