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$
4
  • 1
    $\begingroup$ Mergesort will do. $\endgroup$ Commented May 21, 2014 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$ Commented May 21, 2014 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$ Commented May 21, 2014 at 19:48
  • $\begingroup$ $n!$ grows a little slower than $n^n$, but $\log(n!)$ and $\log(n^n)$ are asymptotically equivalent. $\endgroup$
    – user16034
    Commented Nov 27, 2015 at 13:09

1 Answer 1

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 and acknowledge you have read our privacy policy.

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