Функция слияния алгоритма сортировки слияния не так

Question

Я пытаюсь реализовать mergesort в Java. Я понимаю алгоритм, но у меня проблемы с реализацией. Вот код, который я написал:

package sort; 

import java.util.Arrays; 

public class MergeSort { 

public MergeSort() { 

} 

public static void main(String[] args) { 

    int[] d = {26,14,72,34,622,483}; 
    MergeSort ms = new MergeSort(); 
    int[] results = ms.mergesort(d); 
    for (int i = 0; i < results.length; i++) { 
     System.out.println(results[i]); 
    } 

} 

public int[] mergesort(int[] a) { 

    System.out.println("Another call to merge sort"); 

    if (a.length <= 1) { return a;} 

    int mid = a.length/2; 
    int[] left = Arrays.copyOfRange(a,0,mid); 
    int[] right = Arrays.copyOfRange(a,mid + 1,a.length); 

    left = mergesort(left); 
    right = mergesort(right); 

    int[] result = merge(left,right); 
    return result; 
} 

private int[] merge(int[] b, int[] c) { 
    System.out.println("Another call to merge"); 

    int[] result = new int[b.length+c.length]; 

    if (b.length == 0) { 
     return c; 
    } else if (c.length == 0) { 
     return b; 
    } else if (b[0] < c[0] && b.length == 1) { 
     result[0] = b[0]; 
     for (int i = 1; i < result.length; i++) { 
      result[i] = c[i -1]; 
     } 
     return result; 
    }else if (b[0] > c[0] && c.length == 1) { 
     result[0] = c[0]; 
     for (int i = 0; i < result.length; i++) { 
      result[i] = b[i-1]; 
     } 
     return result; 
    } 
    else if (b[0] < c[0]) { 
     result[0] = b[0]; 
     result = merge(result,merge(Arrays.copyOfRange(b,1,b.length),c)); 
     return result; 
    } else if (b[0] > c[0]) { 
     result[0] = c[0]; 
     result = merge(result,merge(b,Arrays.copyOfRange(c,1,c.length))); 
     return result; 
    } else { 
     System.out.println("Fell to the bottom."); 
     return result; 
    } 
} 

} 

Проблема заключается в моей функции слияния. Я попытался выполнить алгоритм здесь: http://discrete.gr/complexity/, но я продолжал получать IndexOutOfBoundsExceptions, потому что если массив был только размером 1, для захвата нет индекса 1 для Arrays.copyOfRange. Я попытался исправить это в своем коде, но это становится очень грязным. Теперь, как сейчас, это вызовет множество вызовов в функции, а затем выбросит IndexOutOfBoundsException. Я бы очень признателен за помощь в этом. И я просто делаю это самостоятельно, чтобы попытаться понять это, а не как домашнее задание.

Answer 1

Я бы рекомендовал использовать слияние итеративно вместо рекурсивно. Слияние также является плохой функцией concat, которая используется в вашем примере, запутывает (по крайней мере, переводит ее в отдельную функцию).

В вашем случае ошибка здесь:

for (int i = 0; i < result.length; i++) { 
     result[i] = b[i-1]; 
    } 

я должен начать с 1, в противном случае я - 1 == -1, который никогда не является допустимым индексом.

В будущем обратите внимание на то, где исключение возникает в вашем вопросе, и запускайте свою программу через отладчик, в этом случае она немедленно отображает проблему.

EDIT: нормально, что все еще не приводит к правильной программе. Дополнительные ошибки:

int[] right = Arrays.copyOfRange(a,mid + 1,a.length); 
// needs to be "mid", not "mid + 1", read the doc on the function 

edit2: Итоговые строки должны быть:

else if (b[0] < c[0]) { 
    result = merge(new int[]{b[0]},merge(Arrays.copyOfRange(b,1,b.length),c)); 
    return result; 
} else if (b[0] > c[0]) { 
    result = merge(new int[]{c[0]},merge(b,Arrays.copyOfRange(c,1,c.length))); 
    return result; 
} else { 

иначе, результат становится очень долго.