Участник:KulikovM

Свойства и структура алгоритма

Общее описание

Сортировка слиянием упорядочивает набор элементов вида Aᵢ (1 ≤ i ≤ n) путём рекурсивного деления набора на две части и последующего слияния отсортированных половин. В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция merge в каждом узле выполняется последовательно.

Математическое описание

Пусть n ≥ 2. Набор элементов Aᵢ делится на две части:

• левая часть: элементы Aᵢ, где 1 ≤ i ≤ ⌊n/2⌋
• правая часть: элементы Aⱼ, где ⌊n/2⌋ + 1 ≤ j ≤ n

Затем рекурсивно сортируются обе части и выполняется операция слияния.

Базовый случай:

• если n = 1, набор считается уже отсортированным.

Операция слияния (merge)

Операция merge объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.

В процессе слияния используются три индекса:

• i — пробегает левую часть, 1 ≤ i ≤ ⌊n/2⌋
• j — пробегает правую часть, ⌊n/2⌋ + 1 ≤ j ≤ n
• k — позиция результирующего набора, 1 ≤ k ≤ n

Алгоритм слияния (по умолчанию — неубывание):

1. сравниваются элементы Aᵢ и Aⱼ;
2. меньший из них записывается в Aₖ;
3. затем увеличивается индекс (i или j) и индекс k;
4. когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.

• Невозрастание: в шагах сравнения выше используйте знак ≥ вместо ≤ (то есть выбирайте больший элемент).
• Стабильность: при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.

Вычислительное ядро

Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы Aᵢ и Aⱼ и формируется результирующая упорядоченная последовательность в позиции Aₖ. Для невозрастания меняется только знак в сравнении (≥ вместо ≤).

Макроструктура

Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:

• на каждом уровне дерево делит исходный набор элементов на две части,
• каждая ветвь обрабатывается независимо (возможен параллелизм),
• на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.

Таким образом:

• последовательность вычислений на нисходящем этапе — разбиение набора по индексам,
• последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.

Схема последовательной реализации

В последовательной реализации рекурсивная сортировка левой части выполняется полностью, затем сортируется правая часть, и лишь после этого вызывается операция merge. Для невозрастания меняется только знак сравнения в merge (≥ вместо ≤).

Последовательная сложность

Общая сложность определяется затратами на:

• разбиение на две части (O(1)),
• сортировку левой части O((n/2) log(n/2)),
• сортировку правой части O((n/2) log(n/2)),
• слияние (линейный проход: k от 1 до n ⇒ O(n)).

Итого: T(n) = O(n log n) по времени и O(n) дополнительная память под результирующую перестановку.

Информационный граф

Информационный граф представляет собой дерево:

Информационный граф сортировки слиянием (n=8)

Ресурс параллелизма

Параллелизм достигается за счёт независимой обработки двух половин набора. На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ). Высота параллельной части определяется глубиной рекурсии: O(log n).

Вход/выход

1. Вход: массив A из n сравнимых элементов.
2. Выход: тот же массив, отсортированный по неубыванию (по умолчанию) либо по невозрастанию (если в merge поменять ≤ на ≥).

Свойства

• Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).
• Хорошо подходит для больших массивов.
• Естественно поддерживает распараллеливание рекурсивной части.

Программная реализация алгоритма

Последовательная реализация (псевдокод)

procedure MergeSort(A, l, r):
    if r - l + 1 <= 1: return
    m := (l + r) // 2
    MergeSort(A, l, m)
    MergeSort(A, m+1, r)
    Merge(A, l, m, r)            // слияние двух отсортированных фрагментов

// Слияние по неубыванию (для невозрастания заменить ≤ на ≥)
procedure Merge(A, l, m, r):
    i := l           // индекс в левой части
    j := m + 1       // индекс в правой части
    k := 0           // индекс во временном буфере B[0 .. r-l]
    B := new array of size (r - l + 1)

    while i ≤ m and j ≤ r:
        if A[i] ≤ A[j]:          // <-- для невозрастания здесь использовать A[i] ≥ A[j]
            B[k] := A[i]; i := i + 1
        else
            B[k] := A[j]; j := j + 1
        k := k + 1

    while i ≤ m:  B[k] := A[i]; i := i + 1; k := k + 1
    while j ≤ r:  B[k] := A[j]; j := j + 1; k := k + 1

    // копирование результата назад
    for t := 0 .. (r - l):
        A[l + t] := B[t]

Параллельная реализация (последовательно-параллельная)

Псевдокод:

procedure PMergeSort(A, l, r):
    if r - l + 1 <= 1: return
    m := (l + r) // 2

    parallel:
        PMergeSort(A, l,   m)     // ветвь 1
        PMergeSort(A, m+1, r)     // ветвь 2
    join

    Merge(A, l, m, r)             // слияние — последовательное

Литература и источники

• Н. Вирт. Алгоритмы и структуры данных. § 2.4 «Сортировка последовательностей» (с. 97). PDF (стр. 97)