Урок 9.4 — Сортировка слиянием (Merge Sort)

Как и Quick Sort, Merge Sort использует стратегию «разделяй и властвуй». Но делает это по-другому.

Алгоритм состоит из двух фаз:

1. Разделение (Divide) — рекурсивно делим массив пополам, пока не получим подмассивы из одного элемента. Один элемент — это уже отсортированный подмассив (trivially sorted).
2. Слияние (Merge) — попарно сливаем отсортированные подмассивы в один отсортированный массив большего размера.

Ключевое отличие от Quick Sort: вся «магия» Merge Sort происходит на стадии слияния, а не разделения. Разделение — простое (делим пополам), а слияние — сложное (нужно объединить два отсортированных массива).

Рассмотрим массив [38, 27, 43, 3, 9, 82, 10]. Сначала делим его до отдельных элементов, потом сливаем обратно.

Фаза 1: Разделение (Divide)

[38, 27, 43, 3, 9, 82, 10]
             ↓
[38, 27, 43, 3]          [9, 82, 10]
     ↓                          ↓
[38, 27]    [43, 3]        [9, 82]    [10]
   ↓          ↓              ↓
[38] [27]   [43] [3]      [9] [82]    [10]

Фаза 2: Слияние (Merge) — обратный ход рекурсии

[38] + [27] → [27, 38]    (слияние двух элементов)
[43] + [3]  → [3, 43]

[27, 38] + [3, 43] → [3, 27, 38, 43]   (слияние двух отсортированных)

[9] + [82] → [9, 82]
[9, 82] + [10] → [9, 10, 82]

[3, 27, 38, 43] + [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]  ✓

Обрати внимание: на каждом шаге слияния мы объединяем два уже отсортированных массива. Это позволяет нам выполнить слияние за O(n) — просто идём двумя указателями по массивам и выбираем меньший элемент.

Слияние двух отсортированных массивов — это сердце Merge Sort. Представь, что у тебя две стопки отсортированных карт, и ты хочешь объединить их в одну отсортированную стопку.

Алгоритм слияния:

1. Создаём временный массив достаточного размера.
2. Ставим два указателя — на начало левого и правого подмассивов.
3. Сравниваем элементы под указателями. Меньший копируем во временный массив и двигаем соответствующий указатель.
4. Когда один из подмассивов закончился — копируем оставшиеся элементы из другого подмассива.
5. Копируем временный массив обратно в исходный.

static void Merge(int[] arr, int left, int mid, int right)
{
    // Размеры двух подмассивов
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Создаём временные массивы
    int[] leftArr = new int[n1];
    int[] rightArr = new int[n2];

    // Копируем данные во временные массивы
    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        rightArr[j] = arr[mid + 1 + j];

    // Слияние: три указателя
    int iLeft = 0;      // указатель для leftArr
    int iRight = 0;     // указатель для rightArr
    int k = left;       // указатель для основного массива

    while (iLeft < n1 && iRight < n2)
    {
        if (leftArr[iLeft] <= rightArr[iRight])
        {
            arr[k] = leftArr[iLeft];
            iLeft++;
        }
        else
        {
            arr[k] = rightArr[iRight];
            iRight++;
        }
        k++;
    }

    // Копируем оставшиеся элементы из leftArr
    while (iLeft < n1)
    {
        arr[k] = leftArr[iLeft];
        iLeft++;
        k++;
    }

    // Копируем оставшиеся элементы из rightArr
    while (iRight < n2)
    {
        arr[k] = rightArr[iRight];
        iRight++;
        k++;
    }
}

Разберём работу Merge на примере: левая часть [27, 38], правая часть [3, 43].

leftArr = [27, 38]   rightArr = [3, 43]   result = [ _ , _ , _ , _ ]
                                                     ↑ k

Шаг 1: iLeft=0 (27), iRight=0 (3). 3 <= 27 → берём 3
  result = [3, _ , _ , _ ], iRight=1, k=1

Шаг 2: iLeft=0 (27), iRight=1 (43). 27 <= 43 → берём 27
  result = [3, 27, _ , _ ], iLeft=1, k=2

Шаг 3: iLeft=1 (38), iRight=1 (43). 38 <= 43 → берём 38
  result = [3, 27, 38, _ ], iLeft=2, k=3

Шаг 4: left закончился (iLeft=2 > n1-1=1).
  Копируем остаток из rightArr: [43]
  result = [3, 27, 38, 43]  ✓

Теперь соединим рекурсивное разделение и функцию Merge в полную реализацию:

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 38, 27, 43, 3, 9, 82, 10 };

        Console.WriteLine("Исходный массив: " + string.Join(", ", arr));

        MergeSort(arr, 0, arr.Length - 1);

        Console.WriteLine("Отсортированный: " + string.Join(", ", arr));
    }

    static 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);

            Console.WriteLine($"Слияние [{left}..{mid}] + [{mid+1}..{right}] → " +
                              string.Join(", ", arr));
        }
    }

    static void Merge(int[] arr, int left, int mid, int right)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        for (int i = 0; i < n1; i++)
            leftArr[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            rightArr[j] = arr[mid + 1 + j];

        int iLeft = 0, iRight = 0, k = left;

        while (iLeft < n1 && iRight < n2)
        {
            if (leftArr[iLeft] <= rightArr[iRight])
                arr[k++] = leftArr[iLeft++];
            else
                arr[k++] = rightArr[iRight++];
        }

        while (iLeft < n1)
            arr[k++] = leftArr[iLeft++];

        while (iRight < n2)
            arr[k++] = rightArr[iRight++];
    }
}

// Вывод:
// Исходный массив: 38, 27, 43, 3, 9, 82, 10
// Слияние [0..0] + [1..1] → [27, 38, 43, 3, 9, 82, 10]
// Слияние [2..2] + [3..3] → [27, 38, 3, 43, 9, 82, 10]
// Слияние [0..1] + [2..3] → [3, 27, 38, 43, 9, 82, 10]
// Слияние [5..5] + [6..6] → [3, 27, 38, 43, 9, 10, 82]
// Слияние [4..4] + [5..6] → [3, 27, 38, 43, 9, 10, 82]
// Слияние [0..3] + [4..6] → [3, 9, 10, 27, 38, 43, 82]
// Отсортированный: 3, 9, 10, 27, 38, 43, 82

Обрати внимание на порядок слияния:

1. Сначала сливаются самые маленькие подмассивы (размером 1).
2. Постепенно размер сливаемых частей растёт: 2, 4, 8...
3. Последнее слияние — двух половинок всего массива.

Merge Sort можно реализовать и без рекурсии — итеративно. Алгоритм «снизу вверх» (bottom-up) начинает с подмассивов размера 1 и последовательно удваивает размер:

static void MergeSortIterative(int[] arr)
{
    int n = arr.Length;

    // size — размер подмассива, начинаем с 1, удваиваем
    for (int size = 1; size < n; size *= 2)
    {
        // left — начало левого подмассива
        for (int left = 0; left < n - size; left += 2 * size)
        {
            int mid = left + size - 1;
            int right = Math.Min(left + 2 * size - 1, n - 1);

            Merge(arr, left, mid, right);
        }

        Console.WriteLine($"size={size}: {string.Join(", ", arr)}");
    }
}

// Вывод:
// size=1: [27, 38, 3, 43, 9, 82, 10]
// size=2: [3, 27, 38, 43, 9, 10, 82]
// size=4: [3, 9, 10, 27, 38, 43, 82]

Итеративная версия:

• Не использует рекурсию — нет риска StackOverflow
• Работает точно так же за O(n log n)
• Сложнее для понимания, но полезен в средах с ограниченным стеком
• Часто используется в системах реального времени

Какой алгоритм выбрать? Давай сравним их по ключевым параметрам:

Когда выбирать Merge Sort:

• Нужна гарантированная скорость O(n log n) (реальное время, критичные системы)
• Доступа много памяти
• Нужна стабильная сортировка
• Сортируются связные списки (linked list)
• Данные находятся на диске (внешняя сортировка)

Когда выбирать Quick Sort:

• Память ограничена (встроенные системы, микроконтроллеры)
• Нужна максимальная скорость на случайных данных
• Можно позволить себе риск O(n²) (со случайным pivot — практически никогда)
• Массив помещается в кэш процессора (хорошая локальность)

Можно ли сделать Merge Sort без O(n) памяти? Технически да, но это сильно замедлит алгоритм. Одна из техник — In-place Merge с использованием бинарного поиска и ротации массива.

Более практичная оптимизация — использовать один большой временный массив и не создавать новые на каждом уровне:

static void MergeSortOptimized(int[] arr)
{
    int[] temp = new int[arr.Length];
    MergeSortRec(arr, temp, 0, arr.Length - 1);
}

static void MergeSortRec(int[] arr, int[] temp, int left, int right)
{
    if (left < right)
    {
        int mid = left + (right - left) / 2;
        MergeSortRec(arr, temp, left, mid);
        MergeSortRec(arr, temp, mid + 1, right);
        MergeOptimized(arr, temp, left, mid, right);
    }
}

static void MergeOptimized(int[] arr, int[] temp, int left, int mid, int right)
{
    // Копируем в temp только один раз
    for (int k = left; k <= right; k++)
        temp[k] = arr[k];

    int i = left;      // указатель на temp (левая часть)
    int j = mid + 1;   // указатель на temp (правая часть)
    int k = left;      // указатель на arr

    while (i <= mid && j <= right)
    {
        if (temp[i] <= temp[j])
            arr[k++] = temp[i++];
        else
            arr[k++] = temp[j++];
    }

    // Копируем остаток левой части
    while (i <= mid)
        arr[k++] = temp[i++];

    // Остаток правой части уже на месте (если был)
}

Преимущества такого подхода:

• Меньше накладных расходов на выделение памяти (один раз создаём массив)
• Лучшая производительность за счёт меньшего количества операций копирования
• Общая сложность по памяти всё равно O(n), но практическая скорость выше

Проверь понимание Merge Sort.