What is best lower bound for comparison sort?

Asked Feb 01 '24 at 10:13

Active Feb 05 '24 at 05:44

Viewed 150 times

Sorting $n$ numbers requires $\lceil \log_2(n!)\rceil$ comparisons and this is asymptotically optimal, but there is an $O(n)$ error term.

What is the best known lower bound for large $n$?

I couldn't even find $\lceil \log_2(n!)\rceil+1$ proved anywhere, but I suspect even $\lceil \log_2(n!)\rceil+\omega(1)$ might be known.
Some useful links: OEIS A036604 of known exact values, Wikipedia page, and Knuth: TAOCP Vol. 3 section 5.3.

asked Feb 01 '24 at 10:13

domotorp

13,931
37
93

4

It appears the error term can be reduced to $o(n)$, see https://cstheory.stackexchange.com/questions/41493/sorting-with-an-average-of-mathrmlgnon-comparisons – Emil Jeřábek Feb 01 '24 at 11:41
I didn't realize this was an open problem, nice! – mathworker21 Feb 01 '24 at 15:15
Are you asking about worst-case or average-case? – mathworker21 Feb 01 '24 at 15:25
1

Worst case is enough for me. – domotorp Feb 01 '24 at 21:48
@domotorp Please @ me so I receive the notification. Also, just to emphasize it, we have equality for $n=21$, so a lower bound of $\lceil \log_2(n!)\rceil + 1$ can only hold for $n > 21$. – mathworker21 Feb 02 '24 at 13:40
@domotorp The wikipedia page you linked to. – mathworker21 Feb 02 '24 at 16:03

What is best lower bound for comparison sort?

0 Answers0