java - 使用合并排序算法所需的最少比较次数？

Question

对于那些熟悉归并排序的人，我正在尝试计算合并两个大小为 n/2 的子数组所需的最少比较次数，其中 n 是原始未排序数组中的项数。

我知道该算法的平均和最坏情况时间复杂度为 O(nlogn)，但我无法计算出所需的确切最小比较次数(以 n 为单位) .

Answer 1

合并步骤的最小比较次数大约为 n/2(顺便说一句，它仍然是 O(n))，假设一个合理的实现一次的列表已被完全遍历。

例如，如果两个实际上已经排序的列表正在合并，那么较大列表的第一个成员将与较小列表进行 n/2 次比较，直到它被耗尽；然后可以复制更大的列表而无需进一步比较。

List 1    List 2    Merged List         Last Comparison
[1, 2, 3] [4, 5, 6] []                  N/A
[2, 3]    [4, 5, 6] [1]                 1 < 4
[3]       [4, 5, 6] [1, 2]              2 < 4
[]        [4, 5, 6] [1, 2, 3]           3 < 4
[]        [5, 6]    [1, 2, 3, 4]        N/A
[]        [6]       [1, 2, 3, 4, 5]     N/A
[]        []        [1, 2, 3, 4, 5, 6]  N/A

请注意，进行了 3 次比较，列表中有 6 个成员。

再次请注意，即使在最佳情况下，合并步骤仍然有效地被视为 O(n)。合并排序算法的时间复杂度为 O(n*lg(n))，因为整个列表的合并步骤为 O(n)，并且发生分/合并具有 O(lg(n)) 级递归。