这是我长期以来一直回避的问题，但即使在阅读了其他答案后，我也无法理解为什么合并排序是O(n*logn(。也许是我忽略了一些愚蠢的东西。
我所理解的是logn来自于二叉树的高度
我不明白的是，为什么树中每一级的高度都需要n个操作
或者我可能完全错误地看待这个问题(？(。
假设我有一种情况，其中n=8:
[1, 5, 2, 3, 4, 8, 1, 9]
然后我构建了二叉树，将每个级别划分为：
最终我会得到(方便排序(：
[1, 5], [2, 3], [4, 8], [1, 9]
我不知道合并这些将如何在第一级上产生8个操作(据我所知，n*log(n(是级别的数量*每个级别的操作数量。前两对的合并：
我最后做了3个操作，即对照1和5检查2。
因为你知道3>2，您不再需要检查第一对中的1
在最坏的情况下，我找不到每2对需要4次操作的情况。那么，你是如何在每个级别上完成8次操作的呢？
我没有数学天赋，目前还在学习
如果我看错了，我很抱歉。
查看将两个列表合并为一个列表的最后一步。如果列表共享相同的长度n/2，则在列表以相同速度收缩的情况下，最多需要n-1个比较来查找一个列表前面的最小元素。否则，您可能会减少操作。与其他层类似，在n个操作以下，这个数字甚至应该略有减少。但O(n-logn(是一个上界，进一步的检验将表明合并排序并不是渐近更好的。
进一步检查：设n=2^k。我们有k层。一层最多有n-1个操作，一层有两次n/2-1个操作。。。直到n/2乘以1运算。我们应该得到n-1+2(n/2-1(+4(n/4-1(…+n/2(1(=n-1+n-2+n-4+…+n-n/2=kn-(1+2+4+…+2^(k-1((=kn-(2^k-1(=n log n-n+1。
n log n比n和1增长得更快，所以我们甚至得到θ(n log n(，因为我们只对增长最快的部分感兴趣。