# is there a sorting algorithm of order $\log n!$

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.

• Mergesort will do. – Rick Decker May 21 '14 at 11:42
• 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.) – Yuval Filmus May 21 '14 at 18:03
• @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. – Steven Stadnicki May 21 '14 at 19:48
• $n!$ grows a little slower than $n^n$, but $\log(n!)$ and $\log(n^n)$ are asymptotically equivalent. – Yves Daoust Nov 27 '15 at 13:09

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!))$.