Исключение arrayoutofbounds - сортировка слиянием (CLRS)

Question

Я пытаюсь реализовать сортировку слиянием в Java, и я написал код, следуя алгоритму, приведенному в книге CLRS. Я продолжаю выводить массив за пределы исключения, когда пытаюсь запустить код. Честно говоря, я не понимаю, какую ошибку я здесь делаю.

package mergesort;
public class MergeSort {

    public static void MergeSort(int [] input, int low, int high){
        if(low<high){
            int mid=(low+high)/2;
            MergeSort(input,low,mid);
            MergeSort(input,mid+1,high);
            Merge(input,low,mid,high);
        }
    }

    public static void Merge(int [] input, int p, int q, int r){

    int n1=q-p+1,n2=r-q;
    int [] L=new int[n1+1];
    int [] R=new int[n2+1];
    for(int i=1;i<=n1;i++){
        L[i]=input[p+i-1];
    }
    for(int j=1;j<=n2;j++){
        R[j]=input[q+j];
    }
    L[n1+1]=-1;
    R[n2+1]=-1;
    int i=1;
    int j=1;
    for(int k=p;k<=r;k++){
        if(L[i]<=R[j]){
            input[k]=L[i];i++;
        }
        else{
            input[k]=R[j];j++;
        }
    }
    }

    public static String arrayToString(int[]input){
        String print="";
        for(int v:input){
            print +=v + " ";
        }
    return print;
    }

    public static void main(String[] args) {

        int input[]={1122,432,13,223,653,8233,7,2210};

        System.out.println(arrayToString(input));
      MergeSort(input,0,(input.length-1));
      System.out.println(arrayToString(input));

    }
}

Answer 1

int [] L=new int[n1+1];
L[n1+1]=-1; // this throws IndexOutOfBoundsException 
int [] R=new int[n2+1];
R[n2+1]=-1; // throws IndexOutOfBoundsException

Вы объявляете массив с n1+1 длина Это означает, что массивы идут от 0 до n1.

Попробуйте следовать соглашениям Java-кода, методы начинаются со строчных букв и имен переменных. Используйте декларативные переменные pqr Трудно следовать тому, что они есть. Код должен быть понятен людям.

Answer 2

Merge алгоритм в CLRS Предположим, что массивы основаны на 1. Однако массивы в Java основаны на 0.

Когда я сталкиваюсь с такой проблемой, я могу сделать одну из следующих вещей.

1. Выделите еще один элемент для каждого массива и отбросьте первый элемент. Как это:

   int[] L = new int[n1 + 1 + 1]; // extra `+1`
   int[] R = new int[n2 + 1 + 1]; // extra `+1`
   // ...
   int[] input = { 0, 1122, 432, 13, 223, 653, 8233, 7, 2210 }; // leading 0
   MergeSort(input, 1, input.length - 1);
   

2. добавлять -1 к каждому массиву доступ. Как это:

   for(int i = 1; i <= n1; i++){
       L[i] = input[p + i - 1 - 1]; // extra `-1`
   }
   // ...
   MergeSort(input, 1, input.length);
   

3. Полностью понять алгоритм. Никаких хитростей. Это предлагаемый подход.