Is there any sorting algorithm that takes order of $\log n!$ in the worst case? I know that this is the lower bound for sorting algorithms using comparison based sorting. I know that there are algorithms of order $n\log n$, but since $n!$ grows much slower than $n^n$, I wish to know of there is any algorithm of this order.
$\begingroup$
$\endgroup$
-
1$\begingroup$ Mergesort will do. $\endgroup$ – Rick Decker May 21 '14 at 11:42
-
$\begingroup$ Follow-up question: is there a comparison sorting algorithm having comparison depth $\lceil \log_2 n! \rceil$? (Assume for simplicity that the input elements are distinct.) $\endgroup$ – Yuval Filmus May 21 '14 at 18:03
-
1$\begingroup$ @YuvalFilmus I believe it's known that the 'precise' bound can't be achieved for all values of $n$; as noted in cstheory.stackexchange.com/questions/21152/… , TAOCP has some discussion of this topic. $\endgroup$ – Steven Stadnicki May 21 '14 at 19:48
-
$\begingroup$ $n!$ grows a little slower than $n^n$, but $\log(n!)$ and $\log(n^n)$ are asymptotically equivalent. $\endgroup$ – Yves Daoust Nov 27 '15 at 13:09
$\begingroup$
$\endgroup$
By Stirling's approximation, $$\log(n!) = n\log n - n + O(\log n) = \Theta(n\log n)\,,$$ so, yes, there are lots of sorting algorithms that run in time $O(\log(n!))$.
answered May 21 '14 at 13:22
