Зачем нужен Merge Sort?

Merge Sort: назначение, преимущества и применение

Что такое Merge Sort

Merge Sort (сортировка слиянием) — это стабильный, разделяй-и-властвуй алгоритм сортировки, который разбивает массив пополам, рекурсивно сортирует части и затем объединяет их.

// Простой пример
int[] arr = {38, 27, 43, 3, 9, 82, 10};
// Шаг 1: разделяем
// [38, 27, 43] | [3, 9, 82, 10]
// Шаг 2: рекурсивно сортируем
// [27, 38, 43] | [3, 9, 10, 82]
// Шаг 3: сливаем
// [3, 9, 10, 27, 38, 43, 82]

Главные причины использования Merge Sort

1. Гарантированная временная сложность O(n log n)

В отличие от Quick Sort или Bubble Sort, Merge Sort всегда работает за O(n log n) — даже в худшем случае:

Algorithm      Best      Average    Worst      Stable
─────────────────────────────────────────────────────
Quick Sort     O(n log n) O(n log n) O(n²)      NO
Merge Sort     O(n log n) O(n log n) O(n log n) YES
Bubble Sort    O(n)      O(n²)      O(n²)      YES
Heap Sort      O(n log n) O(n log n) O(n log n) NO

На практике:

• Массив из 1 млн элементов: ~20 сравнений per элемент
• Quick Sort может упасть до 1 млн × 1 млн в худшем случае
• Merge Sort — всегда ~20 млн операций

2. Стабильность сортировки (stability)

Merge Sort сохраняет относительный порядок равных элементов:

public class Student {
    String name;
    int grade;
    
    Student(String name, int grade) {
        this.name = name;
        this.grade = grade;
    }
}

Student[] students = {
    new Student("Анна", 5),
    new Student("Борис", 5),
    new Student("Валя", 3)
};

// Merge Sort по оценкам
// Результат:
// Student("Валя", 3)     ← 3 < 5
// Student("Анна", 5)     ← Анна сначала, сохраняется порядок
// Student("Борис", 5)    ← Борис вторым

// Quick Sort (нестабильный) может дать:
// Student("Валя", 3)
// Student("Борис", 5)    ← Порядок Анна-Борис нарушен
// Student("Анна", 5)

Это критично при сортировке объектов с несколькими критериями.

3. Параллелизируемость

Делить-и-властвуй подход хорошо распределяется на несколько потоков:

// Можно запустить сортировку левой и правой части параллельно
public class ParallelMergeSort {
    private ExecutorService executor = Executors.newFixedThreadPool(4);
    
    public void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            
            // Сортируем левую часть в одном потоке
            Future<?> leftTask = executor.submit(() -> mergeSort(arr, left, mid));
            
            // Сортируем правую часть в другом потоке (параллельно)
            Future<?> rightTask = executor.submit(() -> mergeSort(arr, mid + 1, right));
            
            // Ждём обе части
            leftTask.get();
            rightTask.get();
            
            // Сливаем
            merge(arr, left, mid, right);
        }
    }
}

Реализация Merge Sort

public class MergeSort {
    
    public static void mergeSort(int[] arr) {
        if (arr.length < 2) return;
        
        mergeSort(arr, 0, arr.length - 1);
    }
    
    private static void mergeSort(int[] arr, int left, int right) {
        // Базовый случай
        if (left >= right) return;
        
        // Разделяем массив пополам
        int mid = left + (right - left) / 2;
        
        // Рекурсивно сортируем левую часть
        mergeSort(arr, left, mid);
        
        // Рекурсивно сортируем правую часть
        mergeSort(arr, mid + 1, right);
        
        // Сливаем отсортированные части
        merge(arr, left, mid, right);
    }
    
    private static void merge(int[] arr, int left, int mid, int right) {
        // Создаём временный массив
        int[] temp = new int[right - left + 1];
        int i = left;      // Указатель левой части
        int j = mid + 1;   // Указатель правой части
        int k = 0;         // Указатель временного массива
        
        // Сливаем две отсортированные части
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        
        // Копируем оставшиеся элементы левой части
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        
        // Копируем оставшиеся элементы правой части
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        
        // Копируем результат обратно в исходный массив
        for (int x = 0; x < temp.length; x++) {
            arr[left + x] = temp[x];
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
        // Output: [3, 9, 10, 27, 38, 43, 82]
    }
}

Когда использовать Merge Sort

Когда НЕ использовать Merge Sort

// ❌ На маленьких массивах (< 100 элементов)
int[] small = {5, 2, 8, 1};  // Quick Sort быстрее

// ❌ Когда памяти критически не хватает
// Merge Sort требует O(n) доп. памяти на слияние
int[] huge = new int[1_000_000_000];  // 4 GB массив
// Доп. 4 GB для слияния — проблема

// ✅ Quick Sort использует O(log n) стека

Merge Sort в JDK

Действительно, Java использует гибридный подход:

// java.util.Arrays.sort() использует Timsort
// Это гибрид Merge Sort + Insertion Sort
public class TimsortExample {
    public static void main(String[] args) {
        Integer[] arr = {38, 27, 43, 3, 9, 82, 10};
        
        // Внутри используется стабильный алгоритм
        Arrays.sort(arr);
        
        // Для примитивов (int[]) — Quick Sort
        int[] primitives = {38, 27, 43};
        Arrays.sort(primitives);  // Нестабильный, но быстрее по памяти
    }
}

Вывод

Зачем нужен Merge Sort:

1. Гарантия O(n log n) — предсказуемая производительность
2. Стабильность — сохранение порядка равных элементов
3. Параллелизация — работает в многопоточных системах
4. Внешняя сортировка — эффективна для больших данных на диске
5. Надёжность — используется в системных библиотеках (Timsort)

Merge Sort — это инженерный выбор, когда нужна надёжность и предсказуемость вместо максимальной скорости.