|
What do you mean by "C++ sort is Quick sort"?
If you are talking about sort() in STL, specification says only that it performs O(n log n) comparisons in the worst case.
Furthermore, quoting the SGI docs on their STL implementation: 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. |