java - 递归时的操作顺序是什么？

Question

我试图理解合并排序算法的java代码，但我真的陷入了 split 阶段。完整代码在这里:

public class Main {

    public static void main(String[] args) {
        int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };

        mergeSort(intArray, 0, intArray.length);

        for (int i = 0; i < intArray.length; i++) {
            System.out.println(intArray[i]);
        }
    }

    // { 20, 35, -15, 7, 55, 1, -22 }
    public static void mergeSort(int[] input, int start, int end) {

        if (end - start < 2) {
            return;
        }

        int mid = (start + end) / 2;
        mergeSort(input, start, mid);
        mergeSort(input, mid, end);
        merge(input, start, mid, end);
    }

    // { 20, 35, -15, 7, 55, 1, -22 }
    public static void merge(int[] input, int start, int mid, int end) {

        if (input[mid - 1] <= input[mid]) {
            return;
        }

        int i = start;
        int j = mid;
        int tempIndex = 0;

        int[] temp = new int[end - start];
        while (i < mid && j < end) {
            temp[tempIndex++] = input[i] <= input[j] ? input[i++] : input[j++];
        }

        System.arraycopy(input, i, input, start + tempIndex, mid - i);
        System.arraycopy(temp, 0, input, start, tempIndex);
    }
}

在以下mergeSort方法中:

public static void mergeSort(int[] input, int start, int end) {

    if (end - start < 2) {
        return;
    }

    int mid = (start + end) / 2;
    mergeSort(input, start, mid);
    mergeSort(input, mid, end);
    merge(input, start, mid, end);
}

有两次对 mergeSort 的递归调用和一次 merge 调用，那么该方法的操作顺序是什么，以及如何在没有任何额外变量的情况下完成拆分保留划分的未排序数据？

Answer 1

使用[]表示分割，| |对于单个运行，{ } 对于合并运行。这是顺序:

                                        level of recursion
[ 20   35  -15    7   55    1  -22]     0
[ 20   35  -15]                         1
| 20|                                   2
     [ 35  -15]                         2
     | 35|                              3
          |-15|                         3
     {-15   35}                         2
{-15   20   35}                         1
               [  7   55    1  -22]     1
               [  7   55]               2
               |  7|                    3
                    | 55|               3
               {  7   55}               2
                         [  1  -22]     2
                         |  1|          3
                              |-22|     3
                         {-22    1}     2
               {-22    1    7   55}     1
{-22  -15    1    7   20   35   55}     0