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)?$
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$– rus9384Commented Jan 15 at 19:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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
-
$\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$– sbhCommented 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$ Commented Jan 23 at 16:50