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

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))级别的递归中。

Answer 2

对于每个比较，您从两个列表中的一个列表中排除一个元素。所以比较的数量至多是两个列表长度的总和。正如Platinum所示，如果达到一个数组的末尾并且另一个数组中仍有项目，则可能会更少。

所以比较的数量在n/2和n之间。

Answer 3

这个答案给出了一个确切的结果，不仅使用一些Landau symbol写的渐近行为。

合并长度米和Ñ的列表至少需要分钟（米，Ñ）比较。原因是，只有当其中一个输入列表已被完全处理时，您才能停止比较元素，即您至少需要迭代两个列表中较小的一个。请注意，这种比较次数仅对于一些输入而言是足够的，所以它是最小的，因为它假设了可能的输入数据的最佳情况。对于最坏情况的输入，你会发现更高的数字，即n ⌈lg n⌉ − 2⌈lg n⌉ + 1。

让Ñ = 2 ^ķ是二的幂。让i成为合并级别，其中0≤i < k。在级i你执行2 ^{ķ - 我 - 1}合并，其中的每一个需要2个^我比较。将这两个数字相乘，可以得出2 ^{k - 1}比较，其等于n/2。总结在ķ水平的合并你NK/2 =（ñ LG ñ）/ 2比较。

现在让n小于2的幂。假设k = 012lg n⌉仍然表示合并级别的数量。与2 ^k的情况相比，您现在每个级别都少了一个比较。这样合并的总数由ķ降低，导致2 ^ķķ/2 - ķ =（2 ^ķ/2 - 1）ķ比较。但是，如果您删除多个元素，导致n = 2 ^k - 2，那么您不会减少最上面的合并数，因为另一个列表已经是较短的合并数。这表明这里的事情可能会变得更加困难。

因此，让我们有一点点的演示程序，我们可以同时使用来检查我们以前的结果，并计算比较了其他值数：

mc = [0, 0]         # dynamic programming, cache previous results 
k = 1          # ceil(lg n) in the loop 
for n in range(2, 128): 
    a = n // 2        # split list near center 
    b = n - a        # compute length of other half list 
    mc.append(mc[a] + mc[b] + min(a, b)) # need to sort these and then merge 
    if (n & (n - 1)) == 0:     # if n is a power of two 
     assert mc[-1] == n*k/2    # check previous result 
     k += 1        # increment k = ceil(lg n) 
print(', '.join(str(m) for m in mc))  # print sequence of comparison counts, starting at n = 0 

这使您可以按以下顺序：

0, 0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 
37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71, 75, 80, 81, 83, 85, 
88, 90, 93, 96, 100, 102, 105, 108, 112, 115, 119, 123, 128, 130, 133, 
136, 140, 143, 147, 151, 156, 159, 163, 167, 172, 176, 181, 186, 192, 
193, 195, 197, 200, 202, 205, 208, 212, 214, 217, 220, 224, 227, 231, 
235, 240, 242, 245, 248, 252, 255, 259, 263, 268, 271, 275, 279, 284, 
288, 293, 298, 304, 306, 309, 312, 316, 319, 323, 327, 332, 335, 339, 
343, 348, 352, 357, 362, 368, 371, 375, 379, 384, 388, 393, 398, 404, 
408, 413, 418, 424, 429, 435, 441 

您可以在On-Line Encyclopedia of Integer Sequences中查找以发现该序列描述total number of 1's in binary expansions of 0, ..., n。这里也有一些公式，但它们不准确（涉及一些Landau符号术语），或者它们依赖于其他一些不重要的序列，或者它们非常复杂。我最喜欢的一个表达了我上面的程序：

a（0）= 0，a（2n）= a（n）+ a（n-1）+ n，a（2n + 1 ）= 2a（n）+ n + 1。 - Ralf Stephan，2003年9月13日

鉴于这些替代方案，我想我会坚持使用上面的脚本来计算这些数字。您可以删除断言以及与此相关的所有内容，依赖于事实a < b，并删除输出以及如果将其包含到更大的程序中。结果应该如下所示：

mc = [0, 0] 
for n in range(2, 1024): 
    a = n // 2 
    mc.append(mc[a] + mc[n - a] + a) 

请注意，例如，对于ñ = 3你只有两个比较。显然这只有在你将两个极值元素与中值元素进行比较时才能起作用，这样你就不必再将极值元素与另一个元素进行比较。这说明了为什么上述计算仅适用于最佳情况输入。最差情况下的输入会让你在某个点上计算最小和最大元素，导致按照n ⌈lg n⌉ − 2⌈lg n⌉ + 1公式计算的三个比较。