MergeSort函数中的Recursion是如何形成栈的？

Question

这是合并排序代码：

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};

        System.out.println("Unsorted Array:");
        printArray(arr);

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("Sorted Array:");
        printArray(arr);
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;

            mergeSort(arr, left, middle);
            mergeSort(arr, middle + 1, right);

            merge(arr, left, middle, right);
        }
    }

    public static void merge(int[] arr, int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        for (int i = 0; i < n1; i++) {
            leftArray[i] = arr[left + i];
        }
        for (int i = 0; i < n2; i++) {
            rightArray[i] = arr[middle + 1 + i];
        }

        int i = 0, j = 0;
        int k = left;

        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

我特别关注

mergeSort(int[] arr, int left, int right)

函数，它递归地调用自身并使用中间索引或

m

来划分数组。 我无法理解堆栈将如何形成，因为有背靠背的两个递归语句和对合并函数的调用。 例如，如果有一个

int[] array = [5, 4, 6, 7, 8, 2, 1]

r 和 l 分别是 array.length - 1 和 0，则满足基本条件 m = 3，并进行第一次递归调用，将

m

分配给

right

。然后进行相同的递归调用，直到不满足基本条件。一旦不满足基本条件，则进行第二次递归调用。我不确定第二个递归调用是否与第一个递归调用并排进行，以及该堆栈将是什么样子，以及在“子数组”上调用合并的顺序。 请帮助展示上述数组的堆栈是什么样子，以及对它们调用合并的顺序。谢谢！

Answer 1

我无法理解堆栈将如何形成，因为有背靠背的两个递归语句和对合并函数的调用

就堆栈而言，进行多少次递归（或非递归）调用并不重要。如果一个函数有两个递归调用，则第一个递归调用必须完全完成（即清除它创建的堆栈帧），然后第二个递归调用才能在全新的“子堆栈”上开始（如果您愿意的话）。堆栈只能压入或弹出，因此堆栈不像分成两个或类似的东西。

我不确定第二个递归调用是否与第一个递归调用并排进行，以及该堆栈会是什么样子，以及在“子数组”上调用合并的顺序

如上所述，多个递归调用是串行发生的，而不是并行发生的。

我不确定“在子数组上调用

merge

的顺序”是什么意思，但是直到两个子数组都递归排序后才调用

merge

。

merge

然后，将两个子数组合并为一个已排序的子数组，履行其对父框架的义务并将控制权返回给其父调用框架。

这是具有 6 个元素的数组上的调用堆栈，与您的类似（整个数组通过调用传递，因此始终相同）：

const printStack = (s, action) => {
  s = [
    ...s.slice(0, -1),
    `${s.at(-1)} (${action})`,
  ];
  console.log(s.reverse().join("\n"));
}

const f = (lo, hi, stack=[]) => {
  stack.push(`f(${lo}, ${hi})`);
  printStack(stack, "push");

  if (lo < hi) {
    let mid = Math.floor((lo + hi) / 2);
    f(lo, mid, stack);
    f(mid + 1, hi, stack);
  }

  printStack(stack, "pop");
  stack.pop();
};

f(0, 6);