给定一个由n个不同数字组成的数组，其中n=2^k，我如何找到并证明比较的最小和最大数量？
比较将在不同的元素之间进行。
我在SO上看到了一些问题，但似乎与我想要的不匹配。
所有的比较都发生在递归的回溯步骤中，当两个相邻的排序子数组合并时。
在最好的情况下，两个排序的子数组(每个大小)可以直接连接在一起，其中一个在另一个之后。在这种情况下，比较是在一个子数组的所有值与另一个子阵列的单个值之间进行的，因此我们可以进行多次比较。
在最坏的情况下，两个排序的子数组需要交织在一起，这样最后一次比较是在两个子数组中的最后两个值之间。总的来说，这是2−1的比较。
现在我们需要将所有阶段的比较(分区大小)相加。
具有元素(2)的数组的最佳比较案例数为：
0+1(/2)+2(/4)+4(/8)+…+(/2)·1=(/2)log2=2−1
最差的比较案例数是其两倍(参见上面的2个术语)，减去：
/2+/4+/8+…+1=−1
因此我们得到：log2−+1=(−1)2+1
总结
最佳情况：2−1
最坏情况：(−1)2+1