Сортировка слиянием

Merge sort делит диапазон пополам, сортирует обе половины и за линейное время сливает их. Используем полуинтервалы [from, to).

static void mergeSort(int[] values) {
    int[] buffer = new int[values.length];
    mergeSort(values, buffer, 0, values.length);
}
 
private static void mergeSort(
        int[] values, int[] buffer, int from, int to
) {
    if (to - from < 2) return;
 
    int middle = from + (to - from) / 2;
    mergeSort(values, buffer, from, middle);
    mergeSort(values, buffer, middle, to);
    merge(values, buffer, from, middle, to);
}
 
private static void merge(
        int[] values, int[] buffer, int from, int middle, int to
) {
    int left = from;
    int right = middle;
    int out = from;
 
    while (left < middle && right < to) {
        if (values[left] <= values[right]) {
            buffer[out++] = values[left++];
        } else {
            buffer[out++] = values[right++];
        }
    }
    while (left < middle) buffer[out++] = values[left++];
    while (right < to) buffer[out++] = values[right++];
 
    System.arraycopy(buffer, from, values, from, to - from);
}

Инвариант слияния

Перед каждой итерацией buffer[from, out) содержит наименьшие уже рассмотренные элементы двух половин в отсортированном порядке. Следующим берется меньший из голов оставшихся диапазонов.

<= выбирает равный элемент из левой половины первым и сохраняет стабильность.

Сложность

• уровней деления: log n;
• работа слияния на каждом уровне: O(n);
• время во всех случаях: O(n log n);
• дополнительный массив: O(n);
• стек рекурсии: O(log n).

Главное преимущество — гарантированное время и стабильность. Цена для массивов — буфер и копирование. Для linked list слияние можно делать перестановкой ссылок.

См. Быстрая сортировка против сортировки слиянием, Merge sorted array.

На собеседовании

• Почему O(n log n)? log n уровней по O(n) слияния.
• Почему алгоритм стабилен? При равенстве первым выбирается элемент левой половины.
• Что является базовым случаем? Диапазон длины меньше двух.
• Дополнительная память массива? O(n).
• Можно ли переиспользовать один buffer? Да, как в примере.