algorithm - 递归合并排序

Question

我正在尝试为类编写一个递归合并排序方法。当我尝试 mergeSort(leftArr) 和 mergeSort(rightArr) 时，我不断收到 stackoverflows。为什么我的基本案例不起作用？

import java.util.Arrays;

public class SortingAlgorithms {
    public static void mergeSort(int[] list){

        int mid = list.length / 2;
        int [] leftArr = new int [mid];
        int [] rightArr;


        if (mid % 2 == 0) {
            rightArr = new int [mid];
        }
        else{
            rightArr = new int [mid + 1];
        }

        if (leftArr.length < 2 && rightArr.length < 2){
            list = mergeHelper(leftArr, rightArr);
        }

        // copying first half of array
        for (int i = 0; i < mid; i++){
            leftArr[i] = list[i];
        }

        // copying second half of array
        int placeHolder = 0;
        for (int i = mid; i < list.length; i++){
            if (placeHolder < rightArr.length) {
                rightArr[placeHolder] = list[i];
                placeHolder++;
            }
        }

        mergeSort(leftArr);
        mergeSort(rightArr);
    }

    public static int[] mergeHelper(int[] leftArr, int[] rightArr){

        int leftIndex = 0;
        int rightIndex = 0;
        int sortedArrayIndex = 0;
        int[] newList = new int[leftArr.length + rightArr.length];

        while (leftIndex < leftArr.length || rightIndex < rightArr.length){
            if (leftIndex < leftArr.length && rightIndex < rightArr.length){
                if(leftArr[leftIndex] > rightArr[rightIndex]){
                    newList[sortedArrayIndex] = rightArr[rightIndex];
                    rightIndex++;
                    sortedArrayIndex++;
                }
                else {
                    newList[sortedArrayIndex] = leftArr[leftIndex];
                    leftIndex++;
                    sortedArrayIndex++;
                }
            }

            else if (leftIndex < leftArr.length && rightIndex == rightArr.length){
                newList[sortedArrayIndex] = leftArr[leftIndex];
                leftIndex++;
                sortedArrayIndex++;
            }

            else if (rightIndex < rightArr.length && leftIndex == leftArr.length){
                newList[sortedArrayIndex] = rightArr[rightIndex];
                rightIndex++;
                sortedArrayIndex++;
            }
        }
        return newList;
    }

    public static void populateArray(int[] list){
        for (int i = 0; i < list.length; i++){
            list[i] = (int) ((Math.random() * 100));
        }
    }

    public static void main(String[] args){

        int [] list = new int [10];
        populateArray(list);
        System.out.println(Arrays.toString(list));
        mergeSort(list);
        System.out.println(Arrays.toString(list));


        //proof that mergeHelper() works
        //      int[] left =  {1,3,5,7,9};
        //      System.out.println(Arrays.toString(left));
        //      int[] right = {0,2,4,6,8};
        //      System.out.println(Arrays.toString(right));
        //      System.out.println(Arrays.toString(mergeHelper(left,right)));

}
}

Answer 1

你的rightArr长度判断不好。更正:

rightArr = new int [list.length - mid];