Сортировка слиянием (MergeSort): стабильность и гарантии

MergeSort рекурсивно делит массив пополам до подмассивов размером 1, затем сливает упорядоченные подмассивы в большие упорядоченные массивы.

public class MergeSort {
    public static void sort(int[] arr) {
        if (arr.length <= 1) return;
        
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        
        sort(left);
        sort(right);
        merge(arr, left, right);
    }
    
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            // Стабильность: сохраняем порядок равных элементов из левой части
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) result[k++] = left[i++];
        while (j < right.length) result[k++] = right[j++];
    }
}

Ключевые характеристики

Устойчивость: Сохраняет относительный порядок равных элементов
Гарантированная сложность: Всегда O(n log n) независимо от входных данных
Дополнительная память O(n): Требует временного массива для слияния
Параллелизуемость: Легко распараллеливается благодаря независимости подзадач

Компромиссы

Память vs Стабильность: За стабильность и гарантии платим дополнительной памятью
Время vs Предсказуемость: Худший случай лучше, чем у QuickSort, но средний часто медленнее

Применение

Сортировка связанных списков (требует O(1) доп. памяти)
Внешняя сортировка больших файлов (слияние отсортированных блоков)
Там, где важна стабильность (многоуровневая сортировка)


#Java #для_новичков #beginner #algorithm #sorted #MergeSort