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$ @chi I mean, it is based on circumstance which one to use in that case. For a very, very large amount of data one could opt with using $10000n$. Who's to say that it would require such a large leading constant also? And yeah also I do realise only accessing RAM/Cache is an $O(1)$ operation in practice. $\endgroup$ – Azxdreuwa May 25 '18 at 21:07
  • $\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

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