STL sorting algorithms

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
 
H

Howard Hinnant

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top