2
$\begingroup$

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.

$\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
7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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