递归自顶向下的归并排序

Question

我试图理解归并排序算法中的递归排序函数。这是我的代码，我几乎可以确定它是正确的（遵循在线课程） 。

    private static void sort(Comparable[] a, Comparable[] aux, int low, int high) {
         if (high <= low) return;
         int mid = low + (high - low) / 2;
         sort (a, aux, low, mid);
         sort (a, aux, mid+1, high);
         merge(a, aux, low, mid, high);
   }

我理解归并排序的过程-它将每个子数组分成两个更小的子数组，重复这个过程直到子数组长度为一（由定义排序），然后合并。然而，这个排序函数使用的实际方法难以理解。也许是因为我不习惯递归函数，但我想知道第一次合并操作发生时的操作顺序和参数是什么。

例如，当它达到对sort(a, aux, low, mid)的第一个递归调用时-它是否会中断操作并不继续下面的第二个sort和merge函数，而是立即使用新参数再次调用sort？在这种情况下，第二次调用sort；sort(a, aux, mid+1, high); 何时发生？

感谢任何帮助。这是我第一次在这里发布，如果有任何格式问题，请告诉我。

- Lyle

Answer 1

当它第一次递归调用sort(a, aux, low, mid)时，它会中断操作并不继续执行下面的第二个sort函数和merge函数吗？相反，它立即使用新参数再次调用sort函数吗？

是的。它为新参数调用函数（递归），一直往下直到它对该部分进行排序。

在这种情况下，第二个调用sort(a, aux, mid+1, high)会在什么时候发生？

在第一个调用完成执行之后。（当第一部分完成排序时）。

- ThisaruG

Answer 2

如果您没有理解，请参考每个步骤的注释：

 if (high <= low) return; // if your high and low numbers are the same then this part of the loop is finished and it will start going back up
 int mid = low + (high - low) / 2;//sets mid
 sort (a, aux, low, mid);//recursively calls itself so that it will eventually hit the first if. This handles from low to mid
 sort (a, aux, mid+1, high); //this handles from mid+1 to high
 merge(a, aux, low, mid, high); //This is where the merge starts. 

如果你真的遇到了困难，我建议你运行一个简单的示例，并在纸上演示它，这样会有所帮助。

- Alex