java - 递归自顶向下合并排序

Question

我正在努力了解归并排序算法中的递归排序函数。这是我的代码，我几乎可以肯定它是正确的(遵循在线类(class))。

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

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

例如，当它遇到对 sort(a, aux, low, mid) 的第一次递归调用时 - 它是否中断操作而不继续进行第二次排序和下面的合并功能，而是立即使用新的再次调用排序参数？在这种情况下，第二次调用什么时候进行排序；排序(a，aux，mid+1，high)；发生？

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

Answer 1

When it hits the FIRST recursive call to sort(a, aux, low, mid) - does it break operation and not proceed to the second sort and the merge functions below, instead immediately calling sort again with the new parameters?

• 是的。它再次为新参数调用函数(递归)，向下直到它对该部分进行排序。

When, in this case, would the second call to sort; sort(a, aux, mid+1, high); occur?

• 在第一个调用完成执行之后。 (当第一部分完成排序时)。