Java归并排序问题：merge返回的有序数组未更新原数组

你的问题核心是sort方法没有将mergesort返回的排序后数组同步回原输入数组。

mergesort方法确实能正确递归拆分、合并并返回排序后的新数组，但sort方法里仅仅调用了mergesort(a)，却没有把返回的结果赋值给原数组a——Java中数组是引用类型，但这里mergesort返回的是全新的数组对象，原数组a的引用并没有指向这个新数组，所以原数组的内容完全没被修改。

修复方案 #

在sort方法中，接收mergesort返回的排序数组，再将其内容拷贝回原数组：

@Override
public void sort(Comparable[] a) {
    if(a == null || a.length <= 1){
        return;
    }
    Comparable[] sortedArray = mergesort(a);
    // 将排序后的数组内容拷贝回原数组
    System.arraycopy(sortedArray, 0, a, 0, a.length);
}

完整修改后的代码 #

@Override
public void sort(Comparable[] a) {
    if(a == null || a.length <= 1){
        return;
    }
    Comparable[] sortedArray = mergesort(a);
    System.arraycopy(sortedArray, 0, a, 0, a.length);
}

@Override
public Comparable[] mergesort(Comparable[] a) {
    int length = a.length;

    if(length <= 1){return a;} //base case

    int middle = length / 2;
    Comparable[] leftArray = new Comparable[middle];
    Comparable[] rightArray = new Comparable[length - middle];
    int l = 0, r = 0;

    for(; l < length; l++){     //copy contents to either left or right side
        if(l < middle){
            leftArray[l] = a[l];
        }
        else{
            rightArray[r] = a[l];
            r++;
        }
    }

    leftArray = mergesort(leftArray);       //sort left side
    rightArray = mergesort(rightArray);      //sort right side
    return merge(leftArray, rightArray);   //merge the two
}

@Override
public Comparable[] merge(Comparable[] a, Comparable[] b) {
    Comparable[] array = new Comparable[a.length + b.length];
    int arrayIndex = 0, aIndex = 0, bIndex = 0;

    while(aIndex < a.length && bIndex < b.length){
        if(less(a[aIndex], b[bIndex])){
            array[arrayIndex] = a[aIndex];
            aIndex++;
        }
        else{
            array[arrayIndex] = b[bIndex];
            bIndex++;
        }
        arrayIndex++;
    }
    while(aIndex < a.length){
        array[arrayIndex] = a[aIndex];
        arrayIndex++;
        aIndex++;
    }
    while(bIndex < b.length){
        array[arrayIndex] = b[bIndex];
        arrayIndex++;
        bIndex++;
    }
    System.out.print("MERGE: ");
    show(array);
    return array;
}

这样修改后，原数组a会被更新为排序后的内容，输入"SORTEXAMPLE"就能得到期望的有序数组"A E E L M O P R S T X"。

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