Сортировка слиянием

Сортировка слиянием (merge sort) делит массив пополам, сортирует половины рекурсивно и сливает их. $T(N)=O(N\log N)$, $M(N)=O(N)$, устойчива.

Зачем нужно

Квадратичные сортировки на $N=10^6$ работают около $10^4$ секунд. Сортировка слиянием — около 0,2 секунды. По теореме о нижней оценке быстрее $N\log N$ сортировка сравнением не бывает — см. Сортировка.

Как работает

Слияние (Merge)

Два отсортированных массива сливаем в один, сохраняя отсортированность. L бежит по A, R — по B, в результат пишем меньший; позиция в результате — L + R, размер результата — lenA + lenB.

функ. Merge(arr, left, M, right, result)
    // A → [left, M)   B → [M, right)   arr ← result
    L = R = 0
    A = arr + left                  // lenA = M − left
    B = arr + M                     // lenB = right − M
    while (L < lenA and R < lenB)
        если A[L] ≤ B[R]            // ≤ — для устойчивости
            result[L + R] = A[L]
            L++
        иначе
            result[L + R] = B[R]
            R++
    while (L < lenA)
        result[L + R] = A[L]
        L++
    while (R < lenB)
        result[L + R] = B[R]
        R++
    for i = 0 ... (L + R)
        arr[i + left] = result[i]

$T(N)=O(N)$, где $N=lenA+lenB$. Своей памяти — $O(1)$: A, B и result созданы не Merge.

Рекурсия

функ. recursiveMergeSort(arr, left, right, buffer)
    // надо отсортировать arr[left; right)
    если right − left = 1           // на доске; правильно — ≤ 1
        return
    M = (right + left) / 2          // M = left + (right − left) / 2
    recursiveMergeSort(arr, left, M, buffer)
    recursiveMergeSort(arr, M, right, buffer)
    Merge(arr, left, M, right, buffer)
 
MergeSort(arr, N)
    buffer = [ ... ]                // размера N
    recursiveMergeSort(arr, 0, N, buffer)
    delete buffer

Деление идёт, пока не останутся N массивов по одному элементу: $N/2^k=1$, $k={\log }_{2}N$ уровней. На каждом уровне слияния вместе стоят $O(N)$.

$T(N)$	$M(N)$	Устойчива
$O(N\log N)$	$O(N)$	да

Не из лекции: доказательства

• Merge верен по инварианту: в result[0..L+R) лежат $L+R$ наименьших элементов по порядку, и все они не больше A[L] и B[R].
• Сортировка верна по сильной индукции по длине отрезка: при длине $\ge 2$ обе половины непустые и короче — см. Рекурсия.
• $O(N\log N)$ для любого N, не только степени двойки: на глубине $t$ части не длиннее $\lceil N/2^t\rceil$, уровней $\lceil {\log }_{2}N\rceil$. Слияние копирует всё на любом входе, поэтому это $\Theta (N\log N)$.
• Память: буфер $O(N)$ плюс стек глубиной $O(\log N)$.
• Устойчивость: при A[L] = B[R] берётся элемент из A, а он в исходном массиве левее.

Полностью — в конспекте L04.

Тонкости

• ≤ в Merge — это и есть устойчивость. С < сортировка остаётся правильной, но равные элементы из правой половины обгоняют левые.
• Merge нельзя писать прямо в arr: уже первый элемент из B ляжет поверх непрочитанного A[L]. Поэтому нужен буфер, и память — $O(N)$, а не $O(1)$, как у квадратичных сортировок.
• Буфер создаётся один раз в обёртке MergeSort и переиспользуется всеми вызовами.
• arr + left — в C++ адрес элемента arr[left]: A и B — окна в тот же массив, а не копии.

Частые ошибки

• База right − left = 1 (как на доске): на пустом массиве recursiveMergeSort(arr, 0, 0, …) вызывает сам себя бесконечно. Нужно ≤ 1.
• (right + left) / 2 в C++ — переполнение int на больших индексах; пишут left + (right − left) / 2, как в бинарном поиске.
• Забыть скопировать result обратно в arr.
• delete вместо delete[] для буфера в C++.