递归自顶向下合并排序

Question

我正在尝试理解递归排序函数，它是mergesort算法的一部分。下面是我的代码，我几乎可以肯定它是正确的(通过在线课程)。

    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);
   }

我理解合并的作用——它将每个子数组分解成两个较小的子数组，重复这个过程，直到子数组的长度为1（根据定义排序），然后合并。然而，这个排序函数用来完成这个任务的实际方法对我来说很难理解。也许是因为我不习惯递归函数，但是我想知道是否有人可以在第一次合并发生时阐明操作的顺序和参数是什么。

例如，当它点击第一个递归调用进行排序（a，aux，low，mid）时，它是否会中断操作而不继续执行下面的第二个排序和合并函数，而是立即使用新参数再次调用排序？在这种情况下，第二次调用什么时候进行排序；排序（a，辅助，中1，高）；发生

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

Answer 1

如果您没有得到任何信息，请对每个步骤进行说明：

 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. 

我发现，如果你真的很困难，可以运行一个简单的示例，并在纸上和笔上通读它。

Answer 2

当它点击第一次递归调用排序（a， aux， low， mid）时，它是否会中断操作，不继续进行第二次排序和下面的合并函数，而是立即使用新参数再次调用排序？

• 是的。它再次调用函数（Recursion）以获取新参数，然后继续下去，直到对该部分进行排序

在这种情况下，什么时候第二次调用排序；排序(a，aux，mid 1，high)；发生？

< li >执行完第一个调用后。(第一部分排序完成时)。