<p>Sorting <span class="math-container">$n$</span> numbers requires <span class="math-container">$\lceil \log_2(n!)\rceil$</span> comparisons and this is asymptotically optimal, but there is an <span class="math-container">$O(n)$</span> error term.</p>
<blockquote>
<p>What is the best known lower bound for large <span class="math-container">$n$</span>?</p>
</blockquote>
<p>I couldn't even find <span class="math-container">$\lceil \log_2(n!)\rceil+1$</span> proved anywhere, but I suspect even <span class="math-container">$\lceil \log_2(n!)\rceil+\omega(1)$</span> might be known.<br />
Some useful links: <a href="https://oeis.org/A036604" rel="nofollow noreferrer">OEIS A036604</a> of known exact values, <a href="https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list" rel="nofollow noreferrer">Wikipedia page</a>, and Knuth: TAOCP Vol. 3 section 5.3.</p>

CC BY-SA 4.0
2024-02-01T11:41:32.193Z
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
CC BY-SA 4.0
2024-02-01T15:15:47.100Z
I didn't realize this was an open problem, nice!
mathworker21
CC BY-SA 4.0
2024-02-01T15:25:30.550Z
Are you asking about worst-case or average-case?
mathworker21
CC BY-SA 4.0
2024-02-01T21:48:52.447Z
Worst case is enough for me.
domotorp
CC BY-SA 4.0
2024-02-02T13:40:53.410Z
@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
CC BY-SA 4.0
2024-02-02T16:03:46.357Z
@domotorp The wikipedia page you linked to.
mathworker21
<reference-request><sorting><worst-case>
What is best lower bound for comparison sort?
domotorp
# What is best lower bound for comparison sort?

(Asked by: username_0 on 2024-02-01)

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](https://oeis.org/A036604) of known exact values, [Wikipedia page](https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list), and Knuth: TAOCP Vol. 3 section 5.3.

**Tags:** reference-request, sorting, worst-case

> **Comments:**
> **username_1**: 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  
> **username_2**: I didn't realize this was an open problem, nice!  
> **username_2**: Are you asking about worst-case or average-case?  
> **username_0**: Worst case is enough for me.  
> **username_2**: @username_0 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$.  
> **username_2**: @username_0 The wikipedia page you linked to.  

---

## 0 answers

