合并排序递归错误

Question

   Mergesort(a,p,r){
     if(p<r){
       int q=[p+r]/2;
       Mergesort(a,p,q);
       Mergesort(a,q+1,r);
       Merge(a,p,q,r);

来自ALgorithms:Cormen一书的介绍 在此我无法理解合并排序算法的递归调用

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

在第一个递归调用中，我得到了三个然后控制从哪里开始我在 2 处将调用下一个函数 mergesort(a,q+1,r) 和 merge(a,p,q , r) ?

Answer 1

假设您的数组是 a = { 2, 4, 6, 1, 8, 5, 3, 7 }。我交换了你提出的数组的两个元素。现在，接下来就是您的程序所做的，一个接一个地调用。

---

第一次调用时p=0, q=7：你的 while 数组是输入。 在第二次调用 p=0, q=3、第三次调用 p=0, q=1.

第四次调用时p=0, q=0：输入是子数组{ 2 }。这个数组只有一个元素，因此是排序的：行 if(p<r) 确保第四次调用在这里结束并控制 returns 到第三次调用。

第三次调用的输入是 { 2, 4 }。我们刚刚结束行 Mergesort(a,p,q);，因此我们知道输入的前半部分已排序。 第五次 调用（第 Mergesort(a,q+1,r); 行）现在将对下半部分进行排序。

在第五次调用时 p=1, q=1。输入再次是长度为 1 的数组，因此默认排序。控制returns到第三次调用

第三次调用现在正在评估行 Merge(a,p,q,r);。前半部分已排序，后半部分已排序：Merge(a,p,q,r); 取这两半并移动元素，确保 whole 子数组从索引 p 到索引 r 已排序。第三次通话结束

第二个调用 { 2, 4, 6, 1 } 有输入。前半部分已排序，现在仍然是后半部分：调用之后输入变为 { 2, 4, 1, 6 }。在调用 Merge 之后，输入变为 { 1, 2, 4, 6 } 并且第二个调用结束，将控制权返回给第一个调用。

第一个调用现在需要对 它的 输入的后半部分进行排序，顺便说一下，这是整个数组。和以前一样完成。