I've been thinking about this question ever since I learnt about the $O(n\log(n))$ sorting algorithms such as MergeSort, QuickSort (average case is pretty much worse case with a good choice of a pivot) and HeapSort. I've been thinking how can we possibly achieve a greater class of efficiency in worst case? Can we do so using specific hardware implementations? A sort that requires a large amount of space? There is indeed RadixSort and BucketSort, but those are only $O(n)$ in specific use cases.

  • $\begingroup$ If it existed, would you use an algorithm with complexity $10000n$ or one with complexity $10 n \log_2 n$? Further, don't forget that there is no real hardware that can implement arrays with true asymptotic $O(1)$ access. Only when we use the RAM model we pretend that it is $O(1)$, because in practice $n$ is never so large that it matters. $\endgroup$ – chi May 25 '18 at 21:01
  • $\begingroup$ Your question is meaningful. I only wanted to point out that, in my contrived example, you need $n>2^{1000} \simeq 10^{301}$ to make the linear algorithm better, which is way more than the estimated number of atoms in our universe. $\endgroup$ – chi May 25 '18 at 21:14
  • 4
    $\begingroup$ Are you aware of the matching lower bound for comparison-based sorting algorithms? $\endgroup$ – Yuval Filmus May 25 '18 at 21:52
  • 1

To expand on what blue-dino wrote, is it indeed impossible to make a general sorting algorithm with worst-case (or even average-case) complexity which is better than $O(n\log(n))$. In this case "general sorting algorithm" refers to the comparison based model of sorting - it means that the only operation our sorting algorithm is allowed to make is a comparison between two elements which tells us what element is bigger/smaller (or equality), but we get no further information.

The proof of this lower bound is based around building a "comparison-tree" with all possible sortings of a group of $n$ different elements, and proving that there will always be a branch of length $O(n\log(n))$, which corresponds to a similarly long computation or run of the algorithm. As I mentioned beforehand, such length can also be proven to be the average length of a branch in the comparison tree, therefore providing a lower limit to the average complexity as well.


No, n lg n is a theoretical lower bound for general sorting. You can get linear time for special cases. A proof of this fact can be found on cormen.


Your Answer

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