Что случилось с этим слиянием?

Question

int[] input = [6,5,4,3,2,1] 
mergeSort(input,0,input.length) 

void mergeSort(int[] A,int p,int r){ 
    if(p < r){ 
     int q = (int) Math.floor((p+r)/2) 
     mergeSort(A,p,q) 
     mergeSort(A,q+1,r) 
     merge(A,p,q,r) 
    } 
} 

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

Это прямая реализация сортировки слияния из книги Introduction to Algorithms. Хотя он выглядит правильно, он заканчивается исключением ArrayIndexOutOfBounds.

Я пытался отладить его, но не смог. Я хотел бы знать, что происходит не так и как исправить.

Runnable Пример: http://ideone.com/GhuuSd

Answer 1

Во-первых, хотя это Groovy, и поэтому отрицательный индекс, выделенный @Useless, не будет генерировать исключение, это указывает на проблему.

Я думаю, что у вас есть две проблемы: РИСКОВАННАЯ: Я не знаком с точной презентации в «Введение в алгоритмы»

1. Ваши показатели в заселить L и R выключены один - они должны быть [p + i] (таким образом, избегая возможной проблемы с отрицательным индексом) и [q + j + 1]. Обратите внимание, что с этой поправкой вам необходимо передать длину-1 в качестве стартового аргумента для r
2. в вашем тесте внизу, чтобы определить, какие из L и R использовать для повторного заполнения элементов A, вы не проверяете для i или j, выходящих за пределы этих массивов (т. е. i> = n1 или j> = n2). В этих случаях (например, один из L или R «исчерпал» членов), вы должны использовать другой массив.

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

int[] input = [6,5,4,3,2,1] 
mergeSort(input,0,input.length-1) 
System.out.println(Arrays.toString(input))  

void mergeSort(int[] A,int p,int r){ 
    if(p < r){ 
     int q = (int) Math.floor((p+r)/2) 
     mergeSort(A,p,q) 
     mergeSort(A,q+1,r) 
     merge(A,p,q,r) 
    } 
} 

void merge(int[] A,int p,int q,int r) { 
    int i = 0 
    int j = 0 
    int n1 = q - p + 1 
    int n2 = r - q 
    int[] L = new int[n1] 
    int[] R = new int[n2] 
    for(;i<n1;i++){ L[i] = A[p+i] } 
    for(;j<n2;j++){ R[j] = A[q+j+1] } 
    i = j = 0 
    for(int k = p; k <= r; k++){ 
     if(j >= n2 || (i < n1 && L[i] < R[j])) { A[k] = L[i++] } 
     else{ A[k] = R[j++] } 
    }  
} 

Answer 2

int i = 0 
... 
for(;i<n1;i++){ L[i] = A[p+i-1] } 

Что такое индекс в А на вашей первой итерации, где р равно нулю?