java - 我正在尝试实现合并排序，但我得到的输出是相同的数组

Question

我正在尝试实现合并排序，但我得到的输出是相同的数组。这个合并排序给了我与输入相同的输出。请帮助。我很确定实现是正确的，我尝试调试它，但是无法找出错误。

已解决:我正在比较 helper[left] 和 helper[mid] 而不是 helper right。感谢人们的帮助。

public class Sort {

  public static void main(String[] args){
     int arr[] = {3,5,6,9,0,2,4};
    Sort sort = new Sort();
    int i=0;
    sort.MergeSort(arr);
    for(i=0;i<arr.length;i++){
        System.out.print(arr[i]);
    }
  }


  private void MergeSort(int[] arr2) {
    // TODO Auto-generated method stub
    int helper[] = new int[arr2.length];

    MergeSort(arr2,helper,0,arr2.length-1);


  }


  private  void MergeSort(int[] arr2,int[] helper,int start, int end) {
    if(start<end){
        int mid = (start+end)/2;
        MergeSort(arr2,helper,start,mid);
        MergeSort(arr2,helper,mid+1,end);
        Merge(arr2,helper,start,mid,end);


    }else{
        //do nothing
    }

  }


  private  void Merge(int[] arr2, int[] helper, int start, int mid, int end) {
    // TODO Auto-generated method stub
    int i;
    for(i=start;i<=end;i++){
        helper[i]=arr2[i];
    }
    i=start;
    int left = start;
    int right = mid+1;
    while(left <= mid && right <= end){
        if(helper[left] <= helper[mid]){
            arr2[i] = helper[left];
            left++;
        }else{
            arr2[i] = helper[right];
            right++;
        }
        i++;
    }
        //move remaining of left to array
        int remaining = mid-left;
        int j;
        for(j=0;j<=remaining;j++){
            arr2[i+j]=helper[left+j];
        }
  }
}

Answer 1

棘手的一个......:-)

您总是将left处的元素与mid处的元素进行比较，而不是right处的元素:

while(left <= mid && right <= end){
    if(helper[left] <= helper[mid]){

应该是

while(left <= mid && right <= end){
    if(helper[left] <= helper[right]){

可选，但更清晰:
此外，正如马特提到的，您缺少从右臂获取剩余值的能力

while (left <= mid)
    arr2[i++] = helper[left++];

while (right <= end) {
    arr2[i++] = helper[right++];

编辑:将右臂追赶标记为可选