我的数组合并排序器无法正常使用包含一些重复值的数组的奇数长度

My Array merge sorter does not work properly with odd number length of the array that includes some duplicate values. For example, for int[] array = {1, 3, 15, 3, 7, 9, 8, 15, 0} the result is {0, 1, 3, 3, 7, 8, 0, 9, 15,}. Can someone tell me where I am wrong?

我的数组合并排序器无法正常使用包含一些重复值的数组的奇数长度。例如,对于int [] array = {1,3,15,3,7,9,8,15,0},结果为{0,1,3,3,7,8,0,9,15, }。谁能告诉我哪里错了?

public static void mergeSort(int[] inputArray) {
    int size = inputArray.length;
    if (size < 2)
        return;
    int mid = size / 2;
    int leftSize = mid;
    int[] left = Arrays.copyOfRange(inputArray, 0, leftSize);
    int[] right = Arrays.copyOfRange(inputArray, leftSize, inputArray.length);
    mergeSort(left);
    mergeSort(right);
    merge(left, right, inputArray);
}

public static void merge(int[] left, int[] right, int[] arr) {
    int leftSize = left.length;
    int rightSize = right.length;
    int i = 0, j = 0, k = 0;
    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < leftSize) {
        arr[k++] = left[i++];
    }
    while (j < leftSize) {
        arr[k++] = right[j++];
    }
}

1 个解决方案

#1

Change this

while (j < leftSize) {
   arr[k++] = right[j++];
}

To

while (j < rightSize) {
   arr[k++] = right[j++];
}