471,595 Members | 1,501 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,595 software developers and data experts.

STL sort implementation

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

Feb 17 '06 #1
1 3302
Varun Kacholia wrote:
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?


(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_sort().
Best

Kai-Uwe Bux
Feb 17 '06 #2

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

40 posts views Thread by Elijah Bailey | last post: by
12 posts views Thread by Eva | last post: by
20 posts views Thread by Xah Lee | last post: by
4 posts views Thread by DancnDude | last post: by
3 posts views Thread by Alexander Widera | last post: by
21 posts views Thread by yeti349 | last post: by
11 posts views Thread by Jeff Schwab | last post: by
reply views Thread by Anwar ali | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.