MergeSort 中最佳案例的键比较数

Question

我真的很困惑如何在 MergeSort 中计算最佳情况下的键比较次数。假设数组输入大小为a，其中a=2^k

Answer 1

由于数组大小是2的幂，所有合并阶段涉及大小相等的切片，都是2的幂。一对长度为p[=35的切片的最小比较次数=] 是 p，例如，如果数组已经排序。

因此 2 的不同次方的比较总数：

• a=1 -> 0 比较
• a=2 -> 1 比较
• a=4 -> 2*1+2 = 4 次比较
• a=8 -> 2*4+4 = 12 次比较
• a=16 -> 2*12+8 = 32 次比较
• a=32 -> 2*32+16 = 80 次比较
• a=2^k -> k * 2^k-1 比较
• a=2^k+1 -> 2 * k * 2^k-1 + 2^k -> (k+1) * 2^k 比较 (QED)

在最好的情况下，合并排序会对长度为 2^k 的数组执行 k * 2^k-1 次比较。