合并排序算法没有完全合并。数组的右侧不与左侧合并

Question

所以我正在尝试在数组上实现 MergeSort 算法。

我的未排序数组是[3, -5, -10, 22, -100, 1]

但是执行的时候是[-5, -10, 3, 22, -100, 1]

显然，数组右侧的位置 4 和 5 没有明显合并。

我在想，也许我没有对数组进行完全分区，这就是它不能正确合并的原因。

下面是我的合并排序代码：

public static void main(String[] args) {
    // TODO Auto-generated method stub

    int [] arr = {3, -5, -10, 22, -100, 1};
    System.out.println("unsorted array is" +Arrays.toString(arr));

    mergeSort(arr, 0, arr.length);

    System.out.println("it is now merged "+ Arrays.toString(arr));
}


public static void mergeSort(int[] arr, int start, int end) {
    // TODO Auto-generated method stub

    if(end -start < 2) {
        return;
    }

    int mid = (start + end)/2;

    //merge the left side of array
    mergeSort(arr, start, mid);

    //merge the right side of the array
    mergeSort(arr,mid +1, end);

    merge(arr, start, mid, end);
}

public static void merge(int [] arr, int start, int mid, int end) {

    //checking
    if(arr[mid -1] <= arr[mid]) {
        return;
    }

    if(start <= end && mid >= start && mid <= end) {

    //creating temporary array
    int [] temp = new int[end -start + 1];

    //initialising values
    int i = start;
    int j = mid;
    int tempIndex = 0;

    while(i < mid && j < end + 1) {
        if(arr[i] > arr[j]) {
            temp[tempIndex] = arr[j];
            j++;
        }

        else {
            temp[tempIndex] = arr[i];
            i ++;
        }
        tempIndex ++;
    }

    //exit while loop

    if(i < mid) {
        //if that is true then loop
        for(; i< mid; i++) {
            temp[tempIndex] = arr[i];
            tempIndex ++;
        }
    }

    else {
        for(;j < end +1; j++) {
            temp[tempIndex] = arr[j];
            tempIndex ++;
        }
    }

    //copy back into array

    for (int k = start;k <= end; k++) {
        arr[k] = temp[k-start];
    }

    }
}}

Answer 1

纠正两点：主要：

mergeSort(arr, 0, arr.length);

至：

mergeSort(arr, 0, arr.length-1);

并在 mergeSort 方法中

//merge the right side of the array
mergeSort(arr, mid+1, end);

至：

//merge the right side of the array
mergeSort(arr, mid, end);

问题是你总是提供更多的数组元素（元素从 0 到 arr.length-1）并且当分割数组中的元素是偶数时你忽略递归树中的最后一个分割。（所以你跳过了数组右侧部分的合并）

合并排序算法没有完全合并。数组的右侧不与左侧合并

Merge sort Algorithm isn't fully merging. The right side of the array isn't merging with the left side

java

arrays

sorting

mergesort