java - 非迭代合并排序算法的合并异常

Question

我正在尝试创建 MergeSort 的非递归版本，但由于某种原因，合并使代码无法完整运行。

合并排序代码:

public void mergeSort(int[] input)
{

    int n = input.length;
    int size;
    int l;
    for (size = 1; size <= n-1; size = 2*size)
    {
        for (l = 0; l < n-1; l += 2*size)
        {
            int m = l + size -1;
            int r = minimum(l + 2*size - 1, n-1);
            merge(input, l, m, r);
        }
    }       
}

合并代码:

public static void merge(int[] numbers, int low, int middle, int high)
{

    // Copy both parts into the helper array
     int helper[];
    helper = new int[numbers.length];

   for (int i = low; i <= high; i++) {
       helper[i] = numbers[i];
   }


   int i = low;
   int j = middle + 1;
   int k = low;
   // Copy the smallest values from either the left or the right side back
   // to the original array

   while (i <= middle && j <= high) {
       if (helper[i] <= helper[j]) {
            numbers[k] = helper[i];
            i++;
       } else {
            numbers[k] = helper[j];
            j++;
       }

       k++;
     }
     // Copy the rest of the left side of the array into the target array

     while (i <= middle) {
           numbers[k] = helper[i];
           k++;
           i++;
     }
 }

这就是我填充输入数组(大小为 100)的方式:

public static int fillArray()
{
    Random r = new Random();
    int rand = r.nextInt();
    return rand;
}
 //followed by these lines of code in the main method:

    int[] arr;

    arr = new int[100];

    for(int i =0; i<arr.length; i++)
    {
        arr[i] = fillArray();
    }

异常(exception)是 merge() 中的 numbers[k] = helper[i]。

我知道输入数组的内容很好，因为我在对其执行合并排序之前打印出了数组的内容。有谁知道问题是什么？

Answer 1

修复 mergeSort() 中的 m，如下所示:

int m = Math.min(l + size - 1, n - 1);