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