合并排序算法（合并数组部分）

Question

问题是关于从16:43到23:34的视频中的合并排序http://youtu.be/M814OagXWTI?t=16m43s

在退出左/右排序合并递归后，我不清楚我们是如何合并回这些子数组的。让我们从最底部开始，当我们的元素被分成两个子数组时，一个左子数组称为B，一个右子数组称为C。在16:43左右，我们跳转到合并函数，对数组B和C进行排序，这两个数组只有8和3。合并排序函数（下面的代码）基本上通过索引比较B和C的元素。从元素0开始，我们比较两个数组中的每个元素，并将最小的元素添加到数组A中。我们增加元素来自哪个数组的索引，等等，直到基本上有一个排序数组。在我们的排序数组完成之后，我们退出了递归调用，我们在其中爬行回到之前暂停的递归堆栈，继续拆分子数组8 3 2 9的右侧。

我们基本上做了上面所做的，然后再次退出我们所处的递归调用，继续合并38229。好的，这是我的问题：我在代码中看到了一个矛盾。我们将合并的元素反馈给数组A，但是当我们调用merge函数合并28和29时，我们传递的是数组B、C和A。然后我们使用数组B和C进行比较，但是我们要排序的元素在A中，不是吗？那么，这难道不是在分类错误的东西吗？我真的需要澄清这一点。

伪代码：

 MergeSort(A[0...n-1]){
if n<=1
    return A;

copy A[0...n/2-1] to B[0...n/2-1]
copy A[n/2...n-1] to C[0...n/2-1]
MergeSort(B[0...(n/2)-1)
MergeSort(C[0...(n/2)-1)
Merge(B,C,A)

Merge(B[0...p-1], C[0...q-1], A[0...p+q-1]){
i=0; j=0; k=0
while( i <p and j<q) do{
    if B[i] <= C[j] {
        A[k]=B[i];
        i=i+1;
    }
    else {
    A[k]=C[j];
    j=j+1;
    }
    k=k+1
}

//Copy leftover element
if i==p
    A[k...p+q-1]=C[j...q-1]
else
    A[k...p+q-1]=B[i...p-1]
}

Answer 1

这是一个使用引用的算法的简单排序的逐条叙述。缩进表示堆栈深度。每个MergeSort或Merge调用都按时间顺序编号。A3表示调用3中的数组。“==”表示“相当于”。“=”表示“有内容”。

假设Top有一个原始数组content{3,4,2,1}。顶部调用合并排序（原始）

MergeSort1(A1==Original={3,4,2,1}) Create B1={3,4} and C1={2,1}
  MergeSort2(A2==B1={3,4}) Create B2={3} and C2={4}
    MergeSort3(A3==B2={3}) Base case, no changes.
    MergeSort4(A4==C2={4}) Base case, no changes.
    Merge5(B5==B2={3},C5==B2={4},A5==A2==B1) Write {3,4} into A5, which is A2, which is B1.
  MergeSort6(A6==C1={2,1}) Create B6={2} and C6={1}
    MergeSort7(A7==B6={2}) Base case, no changes.
    MergeSort8(A8==C6={1}) Base case, no changes.
    Merge9(B9==B6={2},C9==C6={1},A9==A6==C1) Write {1,2} into A9, which is A6, which is C1.
  Merge10(B10==B1={3,4},C10==C1=={1,2},A10==A1==Original) Write {1,2,3,4} into A10, which is A1, which is Original.

所有这些的高级结果是用{1,2,3,4}替换原来的{3,4,2,1}。

要记住的关键点是，每个函数调用都有自己的堆栈框架，有自己的变量，但是它的形式参数映射到实际参数，该参数是调用方框架中的变量或参数。