Quote:Original post by alnite
std::sort( sort, sort+10, std::greater<int> );
Uses quick sort algorithm. Average case is O(n log n). Worst case is O(n2). Unstable.
Or you may want to use introsort, the best sort in most cases, a combination of quick sort and heap sort. STL doesn't have it, so you probably need to do some research first.
Apparently std::sort already does use introsort, older versions used quick sort:
Quote:Originally by SGI's STL docs
Earlier versions of sort used the quicksort algorithm (C. A. R. Hoare, Comp. J. 5, 1962), using a pivot chosen by median of three (R. C. Singleton, CACM 12, 1969). Quicksort has O(N log(N)) average complexity, but quadratic worst-case complexity. See section 5.2.2 of Knuth for a discussion. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley, 1975.) The current implementation of sort, however, uses the introsort algorithm (D. R. Musser, "Introspective Sorting and Selection Algorithms", Software Practice and Experience 27(8):983, 1997.) whose worst case complexity is O(N log(N)). Introsort is very similar to median-of-three quicksort, and is at least as fast as quicksort on average.
