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

Стабильный алгоритм с гарантированной сложностью $O(n \log n)$. Принцип «разделяй и властвуй»: делим массив пополам, сортируем каждую половину, затем сливаем.

Идея алгоритма

Если в массиве 0 или 1 элемент — он уже отсортирован
Делим массив пополам
Рекурсивно сортируем левую и правую половины
Сливаем две отсортированные половины в одну

Разбор

Рекурсивная сортировка

алг mergesort(цел n, цел таб A[0:n-1], цел таб B[0:n-1], цел l, цел r)
нач
    если l >= r то
        выход
    все
    цел m
    m := div(l + r, 2)
    mergesort(n, A, B, l, m)
    mergesort(n, A, B, m + 1, r)
    merge(n, A, B, l, m, r)
кон

l, r — границы сортируемого участка
m — середина: div(l + r, 2) (целочисленное деление)
Сначала сортируем левую часть [l..m], потом правую [m+1..r]
Затем сливаем обе части функцией merge
Массив B — вспомогательный буфер для слияния

Слияние двух отсортированных частей

Сначала копируем участок [l..r] в буфер B:

нц для i от l до r
    B[i] := A[i]
кц

Затем сливаем из B обратно в A, выбирая на каждом шаге меньший из двух элементов:

i := l
j := m + 1
k := l

нц пока (i <= m) и (j <= r)
    если B[i] <= B[j] то
        A[k] := B[i]
        i := i + 1
    иначе
        A[k] := B[j]
        j := j + 1
    все
    k := k + 1
кц

i — указатель на текущий элемент левой половины
j — указатель на текущий элемент правой половины
Берём меньший из B[i] и B[j] и записываем в A[k]

Если левая часть закончилась позже — дописываем остаток:

нц пока i <= m
    A[k] := B[i]
    i := i + 1
    k := k + 1
кц

Правую часть дописывать не нужно — она уже на своём месте в A.

Сложность: $O(n \log n)$ всегда (даже в худшем случае). Стабильная сортировка (сохраняет порядок равных элементов). Требует дополнительный массив размером $n$.

Полная программа

алг main(цел n)
нач
    если n <= 0 то
        вывод "Размер массива должен быть положительным", нс
        выход
    все

    цел таб A[0:n-1]
    заполнить_случайными(n, A)

    цел таб B[0:n-1]

    вывод "Исходный массив:", нс
    печать_массива(n, A)

    mergesort(n, A, B, 0, n - 1)

    вывод "Отсортированный массив:", нс
    печать_массива(n, A)
кон

алг merge(цел n, цел таб A[0:n-1], цел таб B[0:n-1], цел l, цел m, цел r)
нач
    цел i, j, k

    нц для i от l до r
        B[i] := A[i]
    кц

    i := l
    j := m + 1
    k := l

    нц пока (i <= m) и (j <= r)
        если B[i] <= B[j] то
            A[k] := B[i]
            i := i + 1
        иначе
            A[k] := B[j]
            j := j + 1
        все
        k := k + 1
    кц

    нц пока i <= m
        A[k] := B[i]
        i := i + 1
        k := k + 1
    кц

    | хвост правой части уже на месте
кон

алг mergesort(цел n, цел таб A[0:n-1], цел таб B[0:n-1], цел l, цел r)
нач
    если l >= r то
        выход
    все
    цел m
    m := div(l + r, 2)
    mergesort(n, A, B, l, m)
    mergesort(n, A, B, m + 1, r)
    merge(n, A, B, l, m, r)
кон

алг заполнить_случайными(цел n, цел таб A[0:n-1])
нач
    цел i
    нц для i от 0 до n - 1
        A[i] := irnd(100)
    кц
кон

алг печать_массива(цел n, цел таб A[0:n-1])
нач
    цел i
    нц для i от 0 до n - 1
        вывод A[i], " "
    кц
    вывод нс
кон

▶ Запустить пример