如何导出合并两个长度为n/2的排序数组所需的最坏比较数的表达式

Question

合并排序采用分治方法

Answer 1

合并两个长度为/2的排序数组所需的最坏的比较数是−1。

这是因为当两个值被相互比较时，这两个值中的一个将不再用于比较:它是遵循排序顺序的值.而且它不再是合并过程其余部分的一部分。

在最坏的情况下，最后一个比较将是第一个数组的最后一个值和第二个数组的最后一个值。所有其他(−2 )值都已排除在进一步比较之外，因此这意味着我们已经进行了−2比较。现在执行最后一个命令，完成比较计数为−1。

最坏情况输入的例子

 = 10
A = [0, 2, 4, 6, 8]
B = [1, 3, 5, 7, 9]

合并期间的比较：

0  1
2  1
2  3
4  3
4  5
6  5
6  7
8  7
8  9

最佳案例输入的示例

为了更好地理解这一点，最好的情况是当第一个数组的最后一个值小于第二个数组的第一个值时(反之亦然)。这只需进行2次比较。

 = 10
A = [0, 1, 2, 3, 4]
B = [5, 6, 7, 8, 9]

合并期间的比较：

0 5
1 5
2 5
3 5
4 5

现在不需要更多的比较，因为第一个列表没有更多的值；只有第二个列表的值仍然存在:但是它们不需要与任何东西进行比较，它们可以按照当前发生的顺序追加到结果中。

备注

事实上，这个过程作为合并排序的一部分--实现分而治之算法--只是背景信息。在与合并排序无关的其他上下文中，可能需要合并两个排序列表。