By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,750 Members | 1,187 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,750 IT Pros & Developers. It's quick & easy.

STL sorting algorithms

P: n/a
Ark
Is there a standard STL sorting algorithm that guarantees me O(n*log n) in
the worst case?
My understanding is that sort() is based on the quick sort algorithm which
is O(n^2) in the worst case (and I'm only interested in the worst case, not
average) ... maybe something similar to a merge sort ?

thanks in advance

Jul 23 '05 #1
Share this Question
Share on Google+
1 Reply


P: n/a
In article <42195ee3$1_3@aeinews.>, "Ark" <no****@nono.com> wrote:
Is there a standard STL sorting algorithm that guarantees me O(n*log n) in
the worst case?
My understanding is that sort() is based on the quick sort algorithm which
is O(n^2) in the worst case (and I'm only interested in the worst case, not
average) ... maybe something similar to a merge sort ?

thanks in advance
stable_sort comes close. The standard says:
-2- Complexity: It does at most N(log N)^2 (where N == last - first)
comparisons; if enough extra memory is available, it is N log N.


There is that "if" in there...

The make_heap/sort_heap pair I believe gives you an absolute guarantee.
The complexity on make_heap is O(N), and on sort_heap O(N Log N).

-Howard
Jul 23 '05 #2

This discussion thread is closed

Replies have been disabled for this discussion.