Java归并排序递归方法中start与end变量变化的疑问

我编写了如下归并排序的Java代码（曾误标注为插入排序），但对其中的递归方法mergeSort存在疑问：观察代码可知，mergeSort方法中的start和end变量并没有类似start = start+1的显式赋值操作，但从运行输出能看到这两个变量的值在不断变化，我无法理解这一现象的原因。

代码实现 #

public class MergeSort {

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

    public static void mergeSort(int[] input, int start, int end) {
        System.out.println("start = " + start + " ||" + " end = " + end + " ||" + " mid = " +((start+end)/2));
        if (end - start < 2) {
            return;
        }
        int mid = (start + end) / 2;
        mergeSort(input, start, mid);
        mergeSort(input, mid, end );
        merge(input, start, mid, end);
    }

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

运行输出 #

start = 0 || end = 7 || mid = 3
start = 0 || end = 3 || mid = 1
start = 0 || end = 1 || mid = 0
start = 1 || end = 3 || mid = 2
start = 1 || end = 2 || mid = 1
start = 2 || end = 3 || mid = 2
start = 3 || end = 7 || mid = 5
start = 3 || end = 5 || mid = 4
start = 3 || end = 4 || mid = 3
start = 4 || end = 5 || mid = 4
start = 5 || end = 7 || mid = 6
start = 5 || end = 6 || mid = 5
start = 6 || end = 7 || mid = 6

-22 , -15 , 1 , 7 , 20 , 35 , 55 , 

疑问解答 #

这是递归调用的参数传递特性导致的，并非同一个start/end变量被修改：

• 每次调用mergeSort时，都会传入全新的参数值（比如初始调用传0和7，后续调用传0和3、1和3等）。
• Java中方法的参数是局部变量，每个方法调用都会在栈中创建独立的栈帧，栈帧里的start和end是该次调用独有的局部变量，和其他调用的变量互不干扰。
• 你看到的输出，是不同mergeSort调用各自的局部变量值，并非同一个变量被修改。比如：
  1. 初始调用mergeSort(intArray, 0, 7)，它的局部变量start=0、end=7；
  2. 该调用内部计算mid=3，然后调用mergeSort(input, 0, 3)，这个新调用的局部变量start=0、end=3；
  3. 接着这个新调用又调用mergeSort(input, 0, 1)，它的局部变量start=0、end=1，满足终止条件后返回；
  4. 回到上一层调用，继续执行mergeSort(input, 1, 3)，这个调用的局部变量start=1、end=3；
  5. 以此类推，每一层递归都会根据当前的start和end计算mid，再传入新的参数开启下一层调用，最终输出的就是所有调用各自的参数值。

内容的提问来源于stack exchange，提问作者Cristopher Vergara