$\begingroup$
$\endgroup$
4
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.
Raphael
73.3k31 gold badges183 silver badges403 bronze badges
-
1$\begingroup$ Mergesort will do. $\endgroup$Rick Decker– Rick Decker2014年05月21日 11:42:16 +00:00Commented 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$Yuval Filmus– Yuval Filmus2014年05月21日 18:03:30 +00:00Commented 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$Steven Stadnicki– Steven Stadnicki2014年05月21日 19:48:27 +00:00Commented 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– user160342015年11月27日 13:09:57 +00:00Commented Nov 27, 2015 at 13:09
1 Answer 1
$\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, 2014 at 13:22
Explore related questions
See similar questions with these tags.