我用firstHalf和secondHalf方法制作了MergeSort方法；索引0〜中间，中间+1〜结束。但是，这称为StackOverFlow错误

Question

 public static void mergeSort(int[] data) {
    int[] left = firstHalf(data);
    int[] right = secondHalf(data);

    if( data.length > 1) {
            mergeSort(left);
            mergeSort(right);

            merge(data, left, right);  
    } 

}

public static void merge(int[] data, int[] left, int[] right) {    
      int tempArraySize = data.length;
      int mergedNumbers [] = new int[tempArraySize]; //Temp array to take the sorted array
      int mergePos;                    
      int leftPos;
      int rightPos;

      int middle = data.length / 2;

      mergePos = 0;
      leftPos = 0;     // 0 index                
      rightPos = middle + 1; //j is middle index

      while (leftPos <= middle && rightPos <= data.length - 1) {
         if (left[leftPos] < right[rightPos]) {
            mergedNumbers[mergePos] = left[leftPos];
            leftPos++;
         } 
         else {
            mergedNumbers[mergePos] = right[rightPos];
            rightPos++;
         }
         mergePos++;
      }

      // when the right half array finishes sorting
      while (leftPos <= middle) {
         mergedNumbers[mergePos] = left[leftPos];
         leftPos++;
         mergePos++;
      }

      // when the left half array finishes sorting
      while (rightPos <= data.length - 1) {
         mergedNumbers[mergePos] = right[rightPos];
         rightPos++;
         mergePos++;
      }

      // give value to the original array
      for (mergePos = 0; mergePos < tempArraySize; ++mergePos) {
          data[leftPos + mergePos] = mergedNumbers[mergePos];
      }
}

public static int[] firstHalf(int[] data) {
    int[] tempFirst = new int[(data.length / 2) + 1];

    for( int i = 0; i <= data.length / 2; i++) {
        tempFirst[i] = data[i];
    }

    return tempFirst;

}

public static int[] secondHalf(int[] data) {
    int[] tempSecond = new int[(data.length / 2) + 1];

    for( int i = (data.length / 2) + 1; i < data.length; i++) { // Middle to the end
        for(int j = 0; j <= data.length / 2; j++) {
        tempSecond[j] = data[i];
        }
    }

    return tempSecond;

}

这是我做的。我的mergeSort方法使错误“ java.lang.StackOverflowError”我犯了什么错误？我制作了firstHalf和secondHalf方法来获取索引0〜中间和middle + 1 + 1〜结束。这些方法是从原始“数据”数组中获取值的。“合并”方法与常见的MergeSort代码相同。我必须在mergeSort方法中建立一个基本案例吗？

Answer 1

使用这种方法，返回合并的数组更简单。一次性分配临时数组，并使用索引在两个数组之间合并数据，而不是创建临时数组和复制数据，这样会更快。注释中指出的修复程序。

    public static int[] mergeSort(int[] data) {         // fix
        int[] left = firstHalf(data);
        int[] right = secondHalf(data);
        if(data.length < 2)                             // change
            return data;                                // fix
         left = mergeSort(left);                        // fix
         right = mergeSort(right);                      // fix
         return merge(left, right);                     // fix
    }

    public static int[] merge(int[] left, int[] right) {    // fix
        int mergedNumbers [] = new int[left.length+right.length];   // fix
        int mergePos = 0;                               // fix
        int leftPos = 0;                                // fix
        int rightPos = 0;                               // fix

        while (leftPos < left.length && rightPos < right.length) {  // fix
            if (left[leftPos] < right[rightPos]) {
                mergedNumbers[mergePos] = left[leftPos];
                leftPos++;
            } else {
                mergedNumbers[mergePos] = right[rightPos];
                rightPos++;
            }
            mergePos++;
        }
        while (leftPos < left.length) {                 // fix
              mergedNumbers[mergePos] = left[leftPos];
              leftPos++;
              mergePos++;
        }
        while (rightPos < right.length) {               // fix
              mergedNumbers[mergePos] = right[rightPos];
              rightPos++;
              mergePos++;
        }
        return mergedNumbers;                           // fix
    }

    public static int[] firstHalf(int[] data) {
        int j = (data.length/2);                        // fix
        int[] tempFirst = new int[j];                   // fix      
        for(int i = 0; i < tempFirst.length; i++)       // fix
            tempFirst[i] = data[i];
        return tempFirst;
    }

    public static int[] secondHalf(int[] data) {
        int j = (data.length/2);                        // fix
        int[] tempSecond = new int[data.length-j];      // fix
        for(int i = 0; i < tempSecond.length; i++)      // fix
            tempSecond[i] = data[i+j];                  // fix
        return tempSecond;
    }

Wiki文章对自上而下的合并排序具有某种优化的方法：

https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation