Алгоритм на псевдокоде

Слияние q – серии из списка a с r – серией из списка b,

запись результата в очередь c

Слияние (a, q, b, r, c)

DO (q ≠ 0 и r ≠ 0)

IF (a → Data ≤ b → Data)

<Переместить элемент из списка a в очередь c>

q:=q-1

ELSE

<Переместить элемент из списка b в очередь c>

r:=r-1

FI

OD

DO (q > 0)

<переместить элемент из списка a в очередь c>

q:=q-1

OD

DO (r > 0)

<Переместить элемент из списка b в очередь c>

r:=r-1

OD

Для алгоритма слияния серий с длинами q и r необходимое количество сравнений и перемещений оценивается следующим образом

min (q, r) ≤ C ≤ q+r-1, M=q+r

Пусть длина списка S равна степени двойки, т.е. 2^k, для некоторого натурального k. Разобьем последовательность S на два списка a и b, записывая поочередно элементы S в списки а и b. Сливаем списки a и b с образованием двойных серий, то есть одиночные элементы сливаются в упорядоченные пары, которые записываются попеременно в очереди c₀ и c₁. Переписываем очередь c₀ в список a, очередь c₁ – в список b. Вновь сливаем a и b с образованием серий длины 4 и т. д. На каждом итерации размер серий увеличивается вдвое. Сортировка заканчивается, когда длина серии превысит общее количество элементов в обоих списках. Если длина списка S не является степенью двойки, то некоторые серии в процессе сортировки могут быть короче.

Пример.Отсортировать слово методом прямого слияния.

S

К

У

Р

А′

П

О

В

А″

Е′

Л

Е″

Н

А″′

a

К

Р

П

В

Е′

Е″

А″′

b

У

А′

О

А″

Л

Н

a ← c0

К

У

О

П

Е′

Л

А″′

b ←c1

А′

Р

А″

В

Е′′

Н

a ← c0

А′

К

Р

У

Е′

Е″

Л

Н

b ←c1

А″

В

О

П

А″′

a ← c0

А′

А″

В

К

О

П

Р

У

b ←c1

А″′

Е′

Е″

Л

Н

Sc0

А′

А″

А″′

В

Е′

Е″

К

Л

Н

О

П

Р

У

Рисунок 21 Метод прямого слияния

Схематически начальное расщепление последовательности S на списки a и b можно изобразить следующим образом. Ниже приведен алгоритм расщепление на псевдокоде при условии, что список S не пуст.

S

a