java中使合并排序只使用（n/2+1）额外空间的算法

Question

我试图使合并排序只使用（n/2+1）额外的空间和O（n logn）时间。这是我的家庭作业

最初的问题是：

Write the non-recursive version of merge sort. Your program should run in O(n log n) time and use n/2 + O(1) extra spaces.

该程序将把一个数组一分为二，就像普通的合并排序一样
左侧部分将位于另一个数组中，该数组的长度为ceil（n/2），因此它将符合要求
正确的部分将位于原始阵列中。因此，它将是半就地排序
对不起，我不知道如何进一步解释

我认为这基本上是正确的。但我一直在面对边界外的错误
我知道代码很长很乱。有人能帮我吗

我花了大约5个小时来实现这个。请帮帮我

package comp2011.lec6;

import java.util.Arrays;

public class MergeSort {

    public static void printArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            System.out.printf("%d ", arr[i]);
        }
    }

    public static void mergeSort(int[] arr){
        if(arr.length<2) {
            return;
        }
        int n, lBegin, rBegin;
        n = 1;
        int[] leftArr = new int[arr.length - (arr.length/2)];

        while(n<arr.length) {
            lBegin = 0;
            rBegin = n;



            while(rBegin + n <= arr.length) { 
                mergeArrays(arr, lBegin, lBegin+n, rBegin, rBegin+n, leftArr);
                lBegin = rBegin+n;
                rBegin = lBegin+n;
            }
            if(rBegin < arr.length) {
                mergeArrays(arr, lBegin, lBegin+n, rBegin, arr.length, leftArr);
            }
            n = n*2;
        }
    }


    public static void mergeArrays(int[] array, int startL, int stopL, int startR, int stopR, int[] leftArr) {

//          int[] right = new int[stopR - startR + 1];
//          int[] left = new int[stopL - startL + 1];

//          for(int i = 0, k = startR; i < (right.length - 1); ++i, ++k) {
//              right[i] = array[k];
//          }
        System.out.println("==============");
        System.out.println("stopL: " + stopL +" startL: " + startL);
            for(int i = 0, k = startL; i <= (stopL - startL); ++i, ++k) {
                System.out.println(leftArr[i]);
                leftArr[i] = array[k];
            }

//          right[right.length-1] = Integer.MAX_VALUE;
            leftArr[stopL - startL] = Integer.MAX_VALUE;
            System.out.println("leftArr: " + Arrays.toString(leftArr));
            System.out.println("RightArr: " + Arrays.toString(Arrays.copyOfRange(array, startR, stopR)));
            System.out.println("before: " + Arrays.toString(array));

//          for(int k = startL, m = 0, n = startR; k < stopR; ++k) {
            System.out.println("StartL: " + startL + " StartR: " + stopR);
            for(int k = startL, m = 0, n = startR; ( (k < stopR)  ); ++k) {
                System.out.println("k: " + k);
                System.out.println("Left: " + leftArr[m]);
                System.out.println("Right: " + array[n]);
                System.out.println("Array[k] before: " + array[k]);
//              if(leftArr[m] == Integer.MAX_VALUE){
//                  System.out.println("YES");
//              }
                if( (leftArr[m] <= array[n]) || (n >= stopR) ) {
                    System.out.println("Left is smaller than right");
                    array[k] = leftArr[m];
                    m++;
                }
                else {
                    System.out.println("Right is smaller than left");
                    array[k] = array[n];
                    System.out.println("right: " + array[k]);
                    n++;
                }
                System.out.println("Array[k] after: " + array[k]+"\n");
            }
            System.out.println("after " + Arrays.toString(array));
        }

    public static void main(String[] args) {
        int[] array = new int[] { 5, 2, 4, 12, 2, 10, 13, 1, 7 };
        mergeSort(array);
        printArr(array);
    }
}