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

Обозначим n – количество элементов в S

a, b – рабочие списки

c=(c₀, c₁) – массив из двух очередей

p – предполагаемый размер серии

q – фактический размер серии в списке a

r – фактический размер серии в списке b

m – текущее количество элементов в списках a и b

i – номер активной очереди

<Расщепление (S, a, b, n)>

p:=1

DO (p < n)

<инициализация очередей c₀, c₁>

i:=0, m:=n

DO (m > 0)

IF (m ≥ p) q:=p ELSE q:=m FI

m:= m – q

IF (m ≥ p) r:=p ELSE r:=m FI

m:= m – r

<слияние(a, q, b, r, c_i )>

i:=1–i

OD

a:=c₀.Head, b:=c₁.Head

p:=2p

OD

c₀.Tail → next:=NIL

S:=c₀.Head

При инициализации очереди обнуляются указатели, указывающие на начало и на конец очереди, т.е. очередь становится пустой.

Трудоёмкость методапрямого слияния определяется сложностью операции слияния серий. На каждой итерации происходит ровно n перемещений элементов списка и не более n сравнений. Как нетрудно видеть, количество итераций равно . Тогда

C < n , M=n +n.

Дополнительные n перемещений происходят во время начального расщепления исходного списка. Асимптотические оценки для М и С имеют следующий вид

С=О(n log n), М=О(n log n) при n → ∞.

Метод обеспечивает устойчивую сортировку.При реализации для массивов, метод требует наличия второго вспомогательного массива, равного по размеру исходному массиву. При реализации со списками дополнительной памяти не требуется.

6.2 Цифровая сортировка

Другим методом сортировки последовательностей является цифровая сортировка. Пусть дана последовательность из S чисел, представленных в m – ичной системе счисления. Каждое число состоит из L цифр d₁d₂…d_L, 0 ≤ d_i ≤ m – 1, i=1..L. Сначала числа из списка S распределяются по m очередям, причём номер очереди определяется последней цифрой каждого числа. Затем полученные очереди соединяются в список, для которого все действия повторяются, но распределение по очередям производится в соответствии со следующей цифрой и т.д.

Пример. Отсортировать последовательность 31 03′ 20 02 03″ 33 30 21 методом цифровой сортировки. Числа представлены в четверичной системе счисления.

Рисунок 23 Цифровая сортировка