java.lang.StackOverflowError в MergeSort рекурсивный

Question

Я пытаюсь отладить список размером 10.
ascendingSort(list, start, partition) работает хорошо.
, но после повторения ascendingSort(list, start, partition), ascendingSort(list, partition, end) не удалось, его начало, конец не 5 5, а просто 0 1.

public <T extends Comparable<T>> void ascendingSort(List<T> list) {
    ascendingSort(list, 0, list.size());
}

private <T extends Comparable<T>> void ascendingSort
        (List<T> list, int start, int end) {
    if (start == end) {
        return;
    }
    int partition = (start + end) >> 1;
    ascendingSort(list, start, partition);
    ascendingSort(list, partition, end);
    merge(list, start, partition, end);
}

private <T extends Comparable<T>> void merge
        (List<T> list, int start, int partition, int end) {
    List<T> leftList = new ArrayList<>();
    List<T> rightList = new ArrayList<>();
    Collections.copy(leftList, list.subList(start, partition));
    Collections.copy(rightList, list.subList(partition, end));
    int i = 0, j = 0;
    for (int k = start; k < end; k ++) {
        T leftElement = leftList.get(i);
        T rightElement = rightList.get(j);
        if (leftElement.compareTo(rightElement) > 0) {
            list.set(k, rightElement);
            j++;
        } else {
            list.set(k, leftElement);
            i++;
        }
    }
}

Answer 1

В коде есть несколько проблем:

if (start == end) {
    return;
}

неверно, вместо него следует использовать следующий фрагмент кода:

if (end - start < 2) {
    return;
}

Это и стало причиной исключения StackOverflowException.Попробуйте отладить свой код и посмотрите, почему это происходит.

Далее, Collections.copy(leftList, list.subList(start, partition)); не работает для пустых коллекций (leftList пуст в момент создания), я бы рекомендовал передать подсписок какпараметр для конструктора:

List<T> leftList = new ArrayList<>(list.subList(start, partition));
List<T> rightList = new ArrayList<>(list.subList(partition, end));

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