algorithm - 合并在归并排序算法中只调用一次

Question

在这段代码中，第 6 行返回数组 A 的最小左侧部分，它不能被进一步分解(基本情况)& 第 7 行相同，它将数组 A 的右侧部分切割成最小的子数组。我想问的是第 8 行的 Merge 只被调用一次。它如何多次合并所有小子数组。直到我们得到排序好的 A。

假设我有 A[] = {34,567,87,989,0,43,8,233};

第 6 行将分别返回包含 34,567,87,989 的小子数组，第 7 行返回 0,43,8,233 现在第 8 行中的 Merge 仅被调用一次，这些子数组如何多次调用。

例如合并 34、567 和 0,43，然后合并包含 34,567 和 87,989 的子数组等等。

1)Merge-Sort(A,p,r)
2)if p==r 
3)   return 
4)else
5)   q= floor((p+r)/2)
6)   Merge-Sort(A,p,q)
7)   Merge-Sort(A,q+1,r)
8)   Merge(A,p,q,r)

Answer 1

Merge in line 8 is called only once how can it use these subarrays multiple times?

由于 Merge 在要排序的子数组有多个元素的每一层被调用，Merge 将传递相同子数组的重叠部分在“更深层次”的调用级别上工作的算法阶段。

在您的示例中，merge 将这样调用:

Merge(0, 0, 1)             -- Level 3
Merge(1, 1, 2)             -- Level 3
    Merge(0, 1, 2)         -- Level 2
Merge(2, 2, 3)             -- Level 3
Merge(3, 3, 4)             -- Level 3
    Merge(2, 3, 4)         -- Level 2
        Merge(0, 2, 4)     -- Level 1
Merge(4, 4, 5)             -- Level 3
Merge(5, 5, 6)             -- Level 3
    Merge(4, 5, 6)         -- Level 2
Merge(6, 6, 7)             -- Level 3
Merge(7, 7, 8)             -- Level 3
    Merge(6, 7, 8)         -- Level 2
        Merge(4, 6, 8)     -- Level 1
            Merge(0, 4, 8) -- Level 0

我缩进了调用以显示它们在调用堆栈中的位置。

你可以看到数组的每一半都合并了几次。在最后一行的最终合并之前，左侧子数组的两半在第 7 行合并。前半部分依次在第 3 和 6 行合并。最后，在第 1、2、4 行合并，和 5 个合并自动排序的“单元数组”，因为它们只有一个元素。