STL sorting algorithms

[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

[Howard Hinnant]

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