Реализация метода слияния / merge-метода

Question

Я попытался реализовать алгоритм сортировки слиянием. Метод слияния может быть неправильным. Вот мой код:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    mergesort(list, 0, list.size() - 1);
}   

private static <T extends Comparable<? super T>> void mergesort(List<T> list, int i, int j) {
    if (j - i < 1)
        return;
    int mid = (i + j) / 2;
    mergesort(list, i, mid);
    mergesort(list, mid + 1, j);
    merge(list, i, mid, j);
}

private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r) {
    int half = q - p + 1;
    int otherhalf = r - q;

    List<T> left = new ArrayList<T>();
    List<T> right = new ArrayList<T>();

    for (int i = 0; i < half; i++) {
        left.add(i, a.get(p + i));
    }
    for (int i = 0; i < otherhalf; i++) {
        right.add(i, a.get(q + i + 1));
    }

    int leftindex, rightindex, resultindex;
    leftindex = rightindex = resultindex = 0;

    while (leftindex < left.size() || rightindex < right.size()) {

        if (leftindex < left.size() && rightindex < right.size()) {

            if (left.get(leftindex).compareTo(right.get(rightindex)) < 0) {
                a.set(resultindex, left.get(leftindex));
                resultindex++;
                leftindex++;
            } else {
                a.set(resultindex, right.get(rightindex));
                resultindex++;
                rightindex++;
            }
        } else if (leftindex < left.size()) {
            a.set(resultindex, left.get(leftindex));
            resultindex++;
            leftindex++;
        } else if (rightindex < right.size()) {
            a.set(resultindex, right.get(rightindex));
            resultindex++;
            rightindex++;
        }   
    }
}

Я проверял это. В качестве входа я выбираю [5, 6, 1, 4].

Вывод был: [1, 1, 4, 4]:

Кажется, я не попал на позиции 5 и 6 в методе слияния. Поэтому я думаю, я должен что-то увеличить, но я не знаю, где? Кто-нибудь может мне помочь?

Answer 1

Проблема в resultindex инициализируется 0 вместо p.

Вот некоторые другие заметки:

• было бы проще использовать индекс первого исключенного значения для правого предела вместо индекса последнего элемента. Это позволяет избежать + 1 настроек, которые могут быть вызваны одной ошибкой.
• сравнение должно быть if (left.get(leftindex).compareTo(right.get(rightindex)) <= 0) вместо < для обеспечения стабильной сортировки.
• тест else if (rightindex < right.size()) является избыточным.
• Вы можете уменьшить количество тестов, написав 3 цикла: один, если в обеих половинах есть члены, затем один, чтобы скопировать оставшуюся левую половину, и, наконец, один, чтобы скопировать оставшуюся правую половину.
• имена ваших переменных не являются идиоматическими в Java.

Вот исправленная версия:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    mergesort(list, 0, list.size());
}   

private static <T extends Comparable<? super T>> void mergesort(List<T> list, int i, int j) {
    if (j - i < 2)
        return;
    int mid = (i + j) / 2;
    mergesort(list, i, mid);
    mergesort(list, mid, j);
    merge(list, i, mid, j);
}

private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r) {
    int leftLen = q - p;
    int rightLen = r - q;

    List<T> left = new ArrayList<T>();
    List<T> right = new ArrayList<T>();

    for (int i = 0; i < leftLen; i++) {
        left.add(i, a.get(p + i));
    }
    for (int i = 0; i < rightLen; i++) {
        right.add(i, a.get(q + i));
    }

    int leftIndex = 0;
    int rightIndex = 0;
    int resultIndex = p;

    while (leftIndex < leftLen && rightIndex < rightLen) {
        if (left.get(leftIndex).compareTo(right.get(rightIndex)) <= 0) {
            a.set(resultIndex, left.get(leftIndex));
            resultIndex++;
            leftIndex++;
        } else {
            a.set(resultIndex, right.get(rightIndex));
            resultIndex++;
            rightIndex++;
        }
    }
    while (leftIndex < leftLen) {
        a.set(resultIndex, left.get(leftIndex));
        resultIndex++;
        leftIndex++;
    }
    while (rightIndex < rightLen) {
        a.set(resultIndex, right.get(rightIndex));
        resultIndex++;
        rightIndex++;
    }   
}

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

Вот упрощенная версия:

private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r) {
    int half = q - p;
    List<T> left = new ArrayList<T>();

    for (int i = 0; i < half; i++) {
        left.add(i, a.get(p + i));
    }

    int leftIndex = 0;
    int rightIndex = q;
    int resultIndex = p;

    while (leftIndex < half && rightIndex < r) {
        if (left.get(leftIndex).compareTo(a.get(rightIndex)) <= 0) {
            a.set(resultIndex, left.get(leftIndex));
            resultIndex++;
            leftIndex++;
        } else {
            a.set(resultIndex, a.get(rightIndex));
            resultIndex++;
            rightIndex++;
        }
    }
    while (leftIndex < half) {
        a.set(resultIndex, left.get(leftIndex));
        resultIndex++;
        leftIndex++;
    }
}

Дальнейшее упрощение кода:

• динамический List не требуется для массива left,
• некоторые локальные переменные также могут быть опущены
• комбинированный тест делает последний цикл бесполезным.

Вот упрощенный, но потенциально менее читаемый код:

private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r) {
    int i, half = q - p;
    T[] left = new T[half];

    for (i = 0; i < half; i++)
        left[i] = a.get(p + i);

    for (i = 0; i < half; ) {
        if (q == r || left[i].compareTo(a.get(q)) <= 0)
            a.set(p++, left[i++]);
        else
            a.set(p++, a.get(q++));
    }
}