当n增大时，归并排序在最坏情况下是否比快速排序渐近更快？

是的，当n不断增大时，最坏情况下的归并排序算法渐近快于最坏情况下的快速排序算法，你的判断是正确的。

核心原因分析 #

• 渐近时间复杂度的本质是描述算法运行时间随输入规模n增长的速率：
  • 最坏情况下快速排序的时间复杂度为O(n²)，意味着当n足够大时，其运行时间的增长上限是n的平方级。这种情况通常发生在每次选择的基准值都是当前序列的极值，导致划分后的子序列始终是一个空序列和一个长度为n-1的序列，递归深度达到n。
  • 归并排序无论输入情况如何，时间复杂度始终是O(nlogn)，因为它会稳定地将序列均匀划分为两个子序列，递归深度为logn，每一层的合并操作时间开销为O(n)，整体复杂度保持在nlogn级别。
• 当n趋向于无穷大时，nlogn的增长速率远慢于n²：
  举个直观的例子：当n=1000时，nlog₂n≈10000，而n²=1000000；当n=10000时，nlog₂n≈140000，n²=100000000，两者的差距会随着n的增大持续扩大。

补充说明 #

需要注意的是，平均情况下快速排序的实际运行速度通常优于归并排序——这是因为快速排序的常数因子更小，且内存访问模式更符合缓存友好性。但这并不影响最坏情况下的渐近结论：归并排序的复杂度等级更低，因此在n足够大的最坏场景下，归并排序会比快速排序快得多。

内容的提问来源于stack exchange，提问作者ericboy89