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

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();
    }

merge() 中的 numbers[k] = helper[i] 例外。

我知道输入数组的内容没有问题，因为我在对它执行 MergeSort 之前打印出了数组的内容。有谁知道问题出在哪里？

Answer 1

你没有提到你得到了什么异常，但我假设它的数组越界。是什么阻止你的中间变量超过数组的大小？

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

放入调试打印等

Answer 2

像这样修复 mergeSort() 中的 m：

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

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

exception in merge for non-iterative mergesort algorithm

java

arrays

merge

mergesort

non-recursive