Is there a [non-comparative] sorting algorithm, sorting an array in $o(n \log n)$?

Question

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)?$

• rus9384: 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.

Answer 1

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

• sbh: 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.
• Kenneth Kho: @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.