Java实现Merge Sort合并步骤困惑：数组无返回却完成排序？

一、数组无需返回即可完成排序的原因 #

Java的参数传递规则是值传递，但针对不同类型的参数，传递的内容有所区别：

• 对于数组这类引用类型，传递的是数组对象在堆内存中地址的副本。也就是说，Merge方法里的Arr参数和调用方的原数组引用，指向的是同一个堆内存中的数组对象。
• 在Merge方法中对Arr[k]赋值，本质是修改这个共享堆对象里的元素内容，因此不需要返回数组，原数组就能同步得到排序后的结果。

你的归并排序实现里，Merge方法直接操作传入的数组引用指向的堆对象，递归调用结束后原数组自然已经完成排序。

二、inc变量无法在递归中修改的原因 #

测试代码中的inc是int类型，属于基本数据类型：

• 每次递归调用Merge_Sort或printer时，传递的都是inc当前值的副本。
• 在printer里执行inc++，只是修改了这个局部副本的数值，并不会影响调用方原变量的数值。所以递归过程中，inc的数值不会像数组那样被持续修改传递。

归并排序实现代码 #

import java.math.BigInteger;
import java.util.Arrays;
import java.util.List;

public class MergeSorter {
    public BigInteger[] Merge_Sort(BigInteger[] Arr, int start,  int end){
        if(start<end){
            int mid = (start+end)/2;
            Merge_Sort(Arr, start, mid);
            Merge_Sort(Arr, mid+1, end);
            Merge(Arr, start,mid, end);
        }
        return Arr;
    }

    public void Merge(BigInteger[] Arr, int start, int mid, int end){
        int n1 = mid - start+1;
        int n2 = end - mid;

        BigInteger[] left = new BigInteger[n1+1];
        BigInteger[] right = new BigInteger[n2+1];

        for(int i=0; i<n1; i++){
            left[i] = Arr[start+i-1];
        }

        for(int j=0; j<n2; j++){
            right[j] = Arr[mid+j];
        }

        left[n1] =  null;
        right[n2] = null;

        int i=0;
        int j=0;
        for(int k=start-1;k<end; k++ ){
            if(left[i]!=null && right[j]!=null){
                if((left[i].compareTo(right[j])==-1)
                        ||(left[i].compareTo(right[j])==0)){
                    Arr[k] = left[i];
                    i++;
                }else{
                    Arr[k] = right[j];
                    j++;
                }
            }else if(right[j]!=null){
                Arr[k] = right[j];
                j++;
            }else if(left[i]!=null){
                Arr[k] = left[i];
                i++;
            }else{
                break;
            }
        }
    }
}

测试代码 #

public void printer(int inc, int start, int mid, int end){
    inc++;
    System.out.println("inc: "+inc);
    System.out.println("Merge Step Runs with: "+
"Start: "+start+" mid: "+mid+" end: "+end);
}

public void Merge_Sort(int inc, int start,  int end){
    if(start<end){
        int mid = (start+end)/2;
        Merge_Sort( inc, start, mid);
        Merge_Sort( inc, mid+1, end);

        printer( inc,start, mid, end);
    }
}

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