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

Merge Sort — это стабильный алгоритм сортировки с временной сложностью O(n log n) в худшем, среднем и лучшем случаях. Он особенно полезен, когда:

1. Требуется стабильность — сохраняет порядок равных элементов.
2. Работа с большими данными — эффективен для больших массивов, в отличие от Quick Sort, который может деградировать до O(n²).
3. Внешняя сортировка — хорошо работает с данными, которые не помещаются в оперативную память (например, сортировка файлов).

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

void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

void merge(int[] arr, int l, int m, int r) {
    // Логика слияния двух отсортированных подмассивов
}

Недостаток — требует дополнительной памяти O(n) для слияния.