1
$\begingroup$

We have shown that any comparative sorting algorithm has the worst-case complexity of $\Omega(\log (n!)) = \Omega(n \log n)$, as it has to cover all the ways a permutation can be, and according to the pigeonhole principle, there is a case where more than or equal to half of the currently unknown permutations would be unknown after each comparison; but that doesn't apply on non-comparative sorting algorithms. For example, counting sort can sort an array in $O(n + w)$, where $w$ is the maximum element of the array. But all these algorithms are based on at least one another parameter, that are independent of $n$, or at least $n$ doesn't force any upper-bound for those parameters to exist, and can be as large as anything. Is there a non-comparative one, that we can guarantee the worst-case complexity of $o(n \log n)?$

$\endgroup$
1
  • 1
    $\begingroup$ I think it's a long standing open problem if such an algorithm can exist. Which means there is no such algorithm known and no known proof that it can't exist. $\endgroup$
    – rus9384
    Jan 15 at 19:13

1 Answer 1

1
$\begingroup$

Radix sort can sort an array in $O(n.w)$ where $w$ is the key length. As $w$ is $O(\log n)$, this means it can sort an array with the performance of $O(n \log n)$. In fact, every non-comparison sort in the form of $O(n.w)$ or $O(n.k/d)$ is $O(n \log n)$.

https://www.drdobbs.com/architecture-and-design/the-fastest-sorting-algorithm/184404062

$\endgroup$
2
  • $\begingroup$ I asked for an algorithm running in $o(n \log n)$, not just $O(n \log n)$, meaning that the algorithm has the worst-case complexity of $O(n \log n)$, but not $\Omega(n \log n)$. All these algorithms are asymptotically lower-bounded by that. $\endgroup$
    – sbh
    Jan 14 at 7:09
  • 1
    $\begingroup$ @sbh I just realized that by $o(n \log n)$, you are asking for an algorithm faster than $n \log n$. If you allow for parallel processors, there is parallel merge sort with $\log n$ parallel processors, yielding $O(n)$. If you allow for randomness, there is a $O(n \log \log n)$ and $O(n \sqrt{\log \log n})$ for integers by Thorup, and in 2020 there is a $O(n \sqrt{\log n})$ algorithm for real numbers. If you don't intend to allow parallel processors or randomness, please edit the question, and it that case the comment by rus9384 might be true. $\endgroup$ Jan 23 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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