В каких случаях предпочтителен алгоритм сортировки слиянием (Merge Sort)?

Merge Sort предпочтителен в случаях, где важны гарантированная производительность, стабильность и работа с внешней памятью.

Ключевые преимущества и случаи применения:

1. Гарантированная сложность O(n log n): В отличие от QuickSort, который в худшем случае деградирует до O(n²), MergeSort всегда работает за O(n log n). Это критично для систем реального времени.

2. Стабильность: Сохраняет относительный порядок равных элементов. Важно для сортировки по нескольким ключам.

   // До сортировки: [("Anna", 20), ("Bob", 25), ("Alice", 20)]
   // После стабильной сортировки по возрасту:
   // [("Anna", 20), ("Alice", 20), ("Bob", 25)] - порядок "Anna" и "Alice" сохранён.

3. Эффективная внешняя сортировка: Алгоритм легко адаптируется для сортировки данных, не помещающихся в оперативную память (сортировка больших файлов). Данные разбиваются на части, сортируются в памяти и сливаются с диском.

4. Параллелизм: Алгоритм «разделяй и властвуй» идеально подходит для параллельной реализации, так как подмассивы сортируются независимо.

Пример реализации на Java:

public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // Предотвращает переполнение
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right); // Слияние двух отсортированных половин
    }
}

private void merge(int[] arr, int left, int mid, int right) {
    // Создаём временные массивы для левой и правой части
    int[] leftArr = Arrays.copyOfRange(arr, left, mid + 1);
    int[] rightArr = Arrays.copyOfRange(arr, mid + 1, right + 1);

    int i = 0, j = 0, k = left;
    while (i < leftArr.length && j < rightArr.length) {
        if (leftArr[i] <= rightArr[j]) { // Знак <= обеспечивает стабильность
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }
    // Копируем оставшиеся элементы
    while (i < leftArr.length) arr[k++] = leftArr[i++];
    while (j < rightArr.length) arr[k++] = rightArr[j++];
}

Главный недостаток: Требует дополнительной памяти O(n) для операции слияния. Для сортировки в памяти на небольших массивах QuickSort часто быстрее из-за меньших константных множителей.