Я пытаюсь реализовать универсальный алгоритм сортировки слиянием, который использует временный массив для хранения объединенных частей, а затем копирует отсортированные данные.Однако программа продолжает сбой в шаге копирования (последний цикл while) и выдает исключение ArrayIndexOutOfBounds
.Я запутался, почему это происходит!
Я знаю, что для этой программы проще использовать Array.copy, но я пытаюсь потренироваться с циклами.
public static <E extends Comparable<E>> void mergeSort2(E[] array) {
mergeSortHelper2(array, 0, array.length - 1);
}
private static <E extends Comparable<E>> void mergeSortHelper2(E[] array, int firstIndex, int lastIndex) {
if (firstIndex >= lastIndex) {
return;
}
//otherwise divide
int middle = (firstIndex + lastIndex) / 2;
//conquer with recursion
mergeSortHelper2(array, firstIndex, middle);
mergeSortHelper2(array, middle + 1, lastIndex);
//combine: take in the original array, and all indices
merge2(array, firstIndex, middle, middle + 1, lastIndex);
}
private static <E extends Comparable<E>> void merge2(E[] array, int leftFirst, int leftLast, int rightFirst, int rightLast) {
E[] temp = (E[]) Array.newInstance(array.getClass().getComponentType(), (rightLast - leftFirst + 1));
int indexLeft = leftFirst;
int indexRight = rightFirst;
int index = 0;
while (indexLeft <= leftLast && indexRight <= rightLast) {
if (array[indexLeft].compareTo(array[indexRight]) < 0) {
temp[index++] = array[indexLeft++];
}
else {
temp[index++] = array[indexRight++];
}
}
while (indexLeft <= leftLast) {
temp[index++] = array[indexLeft++];
}
while (indexRight <= rightLast) {
temp[index++] = array[indexRight++];
}
int newIndex = 0;
while (newIndex != temp.length - 1) {
array[newIndex++] = temp[newIndex++];
}
}