So, what is the worst case for C++ "sort" function, when does it go to O(n^2) time? I know it's QuickSort, therefore, it's very fast in most cases, but it gets to O(n^2) in special cases. I've tried to figure it out via measurements, but I have trouble interpreting the results. The number of comparisons C++ "sort" does on various permutations

  • 3
    $\begingroup$ I wonder which compiler your using since Introsort is a more common implementation these days. It has a worst case complexity of $\mathcal{O}(n \log n)$. $\endgroup$ – Albjenow Nov 14 '19 at 11:09
  • $\begingroup$ I am using CLANG 9. I must admit I've never heard of Introsort. $\endgroup$ – FlatAssembler Nov 14 '19 at 11:55
  • 2
    $\begingroup$ You don't know it's Quicksort. It could be anything. It's part of the standard library, but has different implementations depending on the vendor. Counting comparisons on an array of size eight is nonsense. Count it on an array of size 1,000,000. $\endgroup$ – gnasher729 Nov 14 '19 at 12:03
  • $\begingroup$ @gnasher729 At least we can eliminate the possibility that it's MergeSort, MergeSort would do the same number of comparisons no matter which permutation it is. $\endgroup$ – FlatAssembler Nov 14 '19 at 13:07
  • 2
    $\begingroup$ @FlatAssembler Do you think the sort function uses the same method for 8 items that it uses for a million? What makes you think that? You are speculating. $\endgroup$ – gnasher729 Nov 14 '19 at 13:38

The worst case for the Quicksort algorithm depends how a pivot is chosen and it can range from $\Theta(n \log n)$ (if you choose the pivot to be the median) to $\Theta(n^2)$ (if the pivot is always a constant number of elements away from the minimum/maximum element).

That said, C++ standards do not mandate any particular implementation of the sort() function. So it is just a "coincidence" that your implementation happens to use Quicksort.

The answer to your question about the worst case depends on which C++ standard you are referring to. Before C++11, sort() was required to take "approximately $O(n \log n)$ comparisons on the average" (whatever "approximately" means) but, since no particular implementation is mandated, you'd have to look at the sources of the standard library you are using.

If you are referring to C++11 or later, then sort() is required to perform $O(n \log n)$ comparisons in the worst case (see Section To be pedantic, you'd still need to inspect the implementation to know what the worst case is (I could imagine a conforming implementation that first checks whether the input array is any specific permutation (or class of permutations), and then sorts it in linear time).

To be even more pedantic: the standard mandates an asymptotic number of comparisons, so I'm not sure whether a sort() function with a running time of $O(2^n)$ (or some weird function of the input) would conform to the standard, as long as it only performs $O(n \log n)$ comparisons...

  • $\begingroup$ I don't know for sure, but I suspect the reason the complexity is specified in terms of comparisons rather than in terms of running time is because the number of comparison is observable within the language (make a comparison function that counts how many times it's called) whereas the running time is not reliably observable (you can make benchmarks, but they also measure aspects of the environment that the C++ implementation does not control). $\endgroup$ – Gilles 'SO- stop being evil' Nov 14 '19 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.