使用Box类compareTo方法实现归并排序出现逻辑错误求助

我尝试用Box类的compareTo方法对Box对象数组执行归并排序，但出现逻辑错误。排序后的数组全是同一个对象：

Width: 67.8 height: 41.5    length: 56.1    Volume: 157848.57
Width: 67.8 height: 41.5    length: 56.1    Volume: 157848.57
Width: 67.8 height: 41.5    length: 56.1    Volume: 157848.57
Width: 67.8 height: 41.5    length: 56.1    Volume: 157848.57
Width: 67.8 height: 41.5    length: 56.1    Volume: 157848.57
Width: 67.8 height: 41.5    length: 56.1    Volume: 157848.57
Width: 67.8 height: 41.5    length: 56.1    Volume: 157848.57
Width: 67.8 height: 41.5    length: 56.1    Volume: 157848.57
Width: 67.8 height: 41.5    length: 56.1    Volume: 157848.57
Width: 67.8 height: 41.5    length: 56.1    Volume: 157848.57

即便修改compareTo方法的逻辑，结果依然不变。以下是我的归并排序实现：

static void mergeSort(Box[] theBoxes) {
    if(theBoxes.length > 1 ){
        Box [] firstHalf = new Box[theBoxes.length/2];
        System.arraycopy(theBoxes, 0 , firstHalf, 0 ,theBoxes.length /2); 
        mergeSort(firstHalf);
        //Merge sort the second half 
        int secondHalfLength = theBoxes.length - theBoxes.length / 2 ; 
        Box [] secondHalf = new Box [secondHalfLength];
        System.arraycopy(theBoxes, 0 , secondHalf, 0 ,secondHalfLength);
        mergeSort(secondHalf);

        merge(firstHalf, secondHalf , theBoxes); 
    }
}

static void merge(Box [] list1, Box [] list2 , Box [] temp ){
    int current1 = 0;
    int current2 = 0;
    int current3 = 0; 

    while (current1 < list1.length && current2 < list2.length){
        if(list1[current1].compareTo(list2[current2])> 0){ 
            temp[current3++] = list1[current1++];
        }else{
            temp[current3++] = list2[current2++];
        }

        while(current1 < list1.length){
            temp[current3++] = list1[current1++];
        }
        while(current2 < list2.length){
            temp[current3++] = list2[current2++];
        }
    }
}

Box类代码（不允许修改）：

public class Box {
  private double width, height, length;
  
  Box(double w, double h, double l){
    width=w;
    height=h;
    length=l;
  }
  
  private double getVolume(){
    return width*height*length;
  }
    
  public int compareTo(Box o){
    double myVol = this.getVolume();
    double thatVol = o.getVolume();
    if (myVol>thatVol)
      return 1;
    else if (myVol<thatVol)
      return -1;
    else
      return 0;
  }
  
  public String toString(){
    return "Width: "+width+
           "\theight: "+height+
            "\tlength: "+length+
            "\tVolume: "+getVolume();
  }
}

1. 数组拆分的核心错误 #

在mergeSort方法中，复制第二半数组时，你从原数组的起始索引0开始复制，而正确的起始位置应该是第一半数组的结束索引theBoxes.length/2。这直接导致firstHalf和secondHalf内容完全重复，排序后合并自然全是同一个元素。

修复后的mergeSort方法：

static void mergeSort(Box[] theBoxes) {
    if(theBoxes.length > 1 ){
        int halfLength = theBoxes.length / 2;
        Box [] firstHalf = new Box[halfLength];
        System.arraycopy(theBoxes, 0 , firstHalf, 0 , halfLength); 
        mergeSort(firstHalf);
        
        int secondHalfLength = theBoxes.length - halfLength; 
        Box [] secondHalf = new Box [secondHalfLength];
        // 从第一半结束的位置开始复制第二半数组
        System.arraycopy(theBoxes, halfLength , secondHalf, 0 , secondHalfLength);
        mergeSort(secondHalf);

        merge(firstHalf, secondHalf , theBoxes); 
    }
}

2. 归并逻辑的错误 #

你将两个收尾用的while循环放在了外层while循环的内部，导致外层循环仅执行一次就会把其中一个数组的剩余元素全部复制，无法完成完整的归并比较。需要将这两个while循环移到外层循环之外。

修复后的merge方法：

static void merge(Box [] list1, Box [] list2 , Box [] temp ){
    int current1 = 0;
    int current2 = 0;
    int current3 = 0; 

    while (current1 < list1.length && current2 < list2.length){
        if(list1[current1].compareTo(list2[current2])> 0){ 
            temp[current3++] = list1[current1++];
        }else{
            temp[current3++] = list2[current2++];
        }
    }
    // 处理剩余元素的循环移到外层循环外
    while(current1 < list1.length){
        temp[current3++] = list1[current1++];
    }
    while(current2 < list2.length){
        temp[current3++] = list2[current2++];
    }
}

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