Файл: Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией.pdf

Анализ быстрой сортировки. Чтобы изучить эффективность быстрой сорти%
ровки, нужно сначала исследовать поведение процесса разделения. После выбора разделяющего значения x
просматривается весь массив. Поэтому выполняется в точности n
сравнений. Число обменов может быть определено с помощью сле%
дующего вероятностного рассуждения.
Если положение разделяющего значения фиксировано и соответствующее значение индекса равно u
, то среднее число операций обмена равно числу элемен%
тов в левой части сегмента, а именно u
, умноженному на вероятность того, что элемент попал на свое место посредством обмена. Обмен произошел, если элемент принадлежал правой части; вероятность этого равна
(n–u)/n
. Поэтому среднее число обменов равно среднему этих значений по всем возможным значениям u
:
M = [S
S
S
S
Su: 0
≤ u ≤ n–1 : u*(n–u)]/n
2
= n*(n–1)/2n – (2n
2
– 3n + 1)/6n
= (n – 1/n)/6
Если нам сильно везет и в качестве границы всегда удается выбрать медиану,
то каждый процесс разделения разбивает массив пополам, и число необходимых для сортировки проходов равно log(n)
. Тогда полное число сравнений равно n*log(n)
, а полное число обменов – n*log(n)/6
Разумеется, нельзя ожидать, что c выбором медианы всегда будет так везти,
ведь вероятность этого всего лишь
1/n
. Но удивительно то, что средняя эффек%
тивность алгоритма Quicksort хуже оптимального случая только на множитель
2*ln(2)
, если разделяющее значение выбирается в массиве случайно.
Однако и у алгоритма Quicksort есть свои подводные камни. Прежде всего при малых n
его производительность не более чем удовлетворительна, как и для всех эф%
фективных методов. Но его преимущество над другими эффективными методами заключается в легкости подключения какого%нибудь простого метода для обработки коротких сегментов. Это особенно важно для рекурсивной версии алгоритма.
Однако еще остается проблема наихудшего случая. Как поведет себя Quicksort тогда? Увы, ответ неутешителен, и здесь выявляется главная слабость этого алго%
Эффективные методы сортировки

Сортировка
92
ритма. Например, рассмотрим неудачный случай, когда каждый раз в качестве разделяющего значения x
выбирается наибольшее значение в разделяемом сег%
менте. Тогда каждый шаг разбивает сегмент из n
элементов на левую часть из n–1
элементов и правую часть из единственного элемента. Как следствие нужно сде%
лать n
разделений вместо log(n)
, и поведение в худшем случае оказывается по%
рядка n
2
Очевидно, что ключевым шагом здесь является выбор разделяющего значения x
. В приведенном варианте алгоритма на эту роль выбирается средний элемент.
Но с равным успехом можно выбрать первый или последний элемент. В этих слу%
чаях наихудший вариант поведения будет иметь место для изначально упоря%
доченного массива; то есть алгоритм Quicksort явно «не любит» легкие задачки и предпочитает беспорядочные наборы значений. При выборе среднего элемента это странное свойство алгоритма Quicksort не так очевидно, так как изначально упорядоченный массив оказывается наилучшим случаем. На самом деле если вы%
бирается средний элемент, то и производительность в среднем оказывается немного лучшей. Хоор предложил выбирать x
случайным образом или брать ме%
диану небольшой выборки из, скажем, трех ключей [2.10] и [2.11]. Такая предос%
торожность вряд ли ухудшит среднюю производительность алгоритма, но она сильно улучшает его поведение в наихудшем случае. Во всяком случае, ясно, что сортировка с помощью алгоритма Quicksort немного похожа на тотализатор,
и пользователь должен четко понимать, какой проигрыш он может себе позво%
лить, если удача от него отвернется.
Отсюда можно извлечь важный урок для программиста. Каковы последствия поведения алгоритма Quicksort в наихудшем случае, указанном выше? Мы уже знаем, что в такой ситуации каждое разделение дает правый сегмент, состоящий из единственного элемента, и запрос на сортировку этого сегмента сохраняется на стеке для выполнения в будущем. Следовательно, максимальное число таких за%
просов и, следовательно, необходимый размер стека равны n
. Конечно, это совер%
шенно неприемлемо. (Заметим, что дело обстоит еще хуже в рекурсивной версии,
так как вычислительная система, допускающая рекурсивные вызовы процедур,
должна автоматически сохранять значения локальных переменных и параметров всех активаций процедур, и для этого будет использоваться скрытый стек.) Выход здесь в том, чтобы сохранять на стеке запрос на обработку более длинной части,
а к обработке короткой части приступать немедленно. Тогда размер стека
M
мож%
но ограничить величиной log(n)
Соответствующее изменение локализовано в том месте программы, где на сте%
ке сохраняются новые запросы на сортировку сегментов:
IF j – L < R – i THEN
IF i < R THEN (* *)
INC(s); low[s] := i; high[s] := R
END;
R := j (*€ *)
ELSE
IF L < j THEN (* *)

93
INC(s); low[s] := L; high[s] := j
END;
L := i (*€ *)
END
2.3.4. Поиск медианы
Медиана (median) n
элементов – это элемент, который меньше (или равен) поло%
вины n
элементов и который больше (или равен) элементов другой половины.
Например, медиана чисел
16 12 99 95 18 87 10
равна
18
. Задача нахождения медианы обычно связывается с задачей сортировки, так как очевидный метод определения медианы состоит в сортировке n
элементов и вы%
боре среднего элемента. Но использованная выше процедура разделения дает потен%
циальную возможность находить медиану гораздо быстрее. Метод, который мы сей%
час продемонстрируем, легко обобщается на задачу нахождения k
%го наименьшего из n
элементов. Нахождение медианы соответствует частному случаю k = n/2
Этот алгоритм был придуман Хоором [2.4] и работает следующим образом.
Во%первых, операция разделения в алгоритме Quicksort выполняется с
L = 0
и
R = n–1
, причем в качестве разделяющего значения x
выбирается a
k
. В результате получаются значения индексов i
и j
– такие, что
1.
a h
< x для всех h < i
2.
a h
> x для всех h > j
3.
i > j
Здесь возможны три случая:
1. Разделяющее значение x
оказалось слишком мало; в результате граница между двумя частями меньше нужного значения k
. Тогда операцию разде%
ления нужно повторить с элементами a
i
... a
R
(см. рис. 2.9).
Рис. 2.9. Значение x слишком мало
2. Выбранное значение x
оказалось слишком велико. Тогда операцию разде%
ления нужно повторить с элементами a
L
... a j
(см. рис. 2.10).
3.
j < k < i:
элемент a
k разбивает массив на две части в нужной пропорции и поэтому является искомым значением (см. рис. 2.11).
Операцию разделения нужно повторять, пока не реализуется случай 3. Этот цикл выражается следующим программным фрагментом:
Эффективные методы сортировки

Сортировка
94
L := 0; R := n;
WHILE L < R–1 DO
x := a[k];
# (a[L] ... a[R–1]);
IF j < k THEN L := i END;
IF k < i THEN R := j END
END
За формальным доказательством корректности алгоритма отошлем читателя к оригинальной статье Хоора. Теперь нетрудно выписать процедуру
Find це%
ликом:
PROCEDURE Find (k: INTEGER);
(* ADruS2_Sorts *)
(* a , a[k] k– *)
VAR L, R, i, j: INTEGER; w, x: Item;
BEGIN
L := 0; R := n–1;
WHILE L < R–1 DO
x := a[k]; i := L; j := R;
REPEAT
WHILE a[i] < x DO i := i+1 END;
WHILE x < a[j] DO j := j–1 END;
IF i <= j THEN
w := a[i]; a[i] := a[j]; a[j] := w;
i := i+1; j := j–1
END
UNTIL i > j;
IF j < k THEN L := i END;
IF k < i THEN R := j END
END
END Find
Рис. 2.10. Значение x слишком велико
Рис. 2.11. Значение x оказалось правильным

95
Если предположить, что в среднем каждое разбиение делит пополам размер той части массива, в которой находится искомое значение, то необходимое число сравнений будет n + n/2 + n/4 + ... + 1
≈ 2n то есть величина порядка n
. Это объясняет эффективность процедуры
Find для нахождения медиан и других подобных величин, и этим объясняется ее превос%
ходство над простым методом, состоящим в сортировке всего массива с последую%
щим выбором k
%го элемента (где наилучшее поведение имеет порядок n*log(n)
).
Однако в худшем случае каждый шаг разделения уменьшает размер множества кандидатов только на единицу, что приводит к числу сравнений порядка n
2
. Как и ранее, вряд ли имеет смысл использовать этот алгоритм, когда число элементов мало, скажем меньше 10.
2.3.5. Сравнение методов сортировки массивов
Чтобы завершить парад методов сортировки, попробуем сравнить их эффектив%
ность. Пусть n
обозначает число сортируемых элементов, а
C
и
M
– число сравне%
ний ключей и пересылок элементов соответственно. Для всех трех простых ме%
тодов сортировки имеются замкнутые аналитические формулы. Они даны в табл. 2.8. В колонках min
, max
, avg стоят соответствующие минимальные, мак%
симальные значения, а также значения, усредненные по всем n!
перестановкам n
элементов.
Таблица 2.8.
Таблица 2.8.
Таблица 2.8.
Таблица 2.8.
Таблица 2.8. Сравнение простых методов сортировки min avg max
Простые
C = n–1
(n
2
+ n – 2)/4
(n
2
– n)/2 – 1
вставки
M = 2(n–1)
(n
2
– 9n –10)/4
(n
2
– 3n – 4)/2
Простой
C = (n
2
– n)/2
(n
2
– n)/2
(n
2
– n)/2
выбор
M = 3(n–1)
n*(ln(n) + 0.57)
n
2
/4 + 3(n–1)
Простые
C = (n
2
–n)/2
(n
2
–n)/2
(n
2
–n)/2
обмены
M = 0
(n
2
–n)*0.75
(n
2
–n)*1.5
Для эффективных методов простых точных формул не существует. Основные факты таковы: вычислительные затраты для Shellsort оцениваются величиной порядка c*n
1.2
, а для сортировок Heapsort и Quicksort – величиной c*n*log(n)
, где c
– некоторые коэффициенты.
Эти формулы дают только грубую оценку эффективности как функцию параметра n
, и они позволяют классифицировать алгоритмы сортировки на примитивные, простые методы (
n
2
) и эффективные, или «логарифмические»,
методы (
n*log(n)
). Однако для практических целей полезно иметь эмпирические данные о величинах коэффициентов c
, чтобы можно было сравнить разные ме%
тоды. Более того, формулы приведенного типа не учитывают вычислительных
Эффективные методы сортировки

Сортировка
96
затрат на операции, отличные от сравнений ключей и пересылок элементов, та%
кие как управление циклами и т. п. Понятно, что эти факторы в какой%то степе%
ни зависят от конкретной вычислительной системы, но тем не менее для ориен%
тировки полезно иметь какие%нибудь эмпирические данные. Таблица 2.9
показывает время (в секундах), затраченное обсуждавшимися методами сорти%
ровки, при выполнении на персональном компьютере Лилит (Lilith). Три ко%
лонки содержат время, затраченное на сортировку уже упорядоченного массива,
случайной перестановки и массива, упорядоченного в обратном порядке. Табли%
ца 2.9 содержит данные для массива из 256 элементов, таблица 2.10 – для масси%
ва из 2048 элементов. Эти данные демонстрируют явное различие между квад%
ратичными (
n
2
) и логарифмическими методами (
n*log(n)
). Кроме того, полезно отметить следующее:
1. Замена простых вставок (
StraightInsertion
) на двоичные (
BinaryInsertion
)
дает лишь незначительное улучшение, а в случае уже упорядоченного мас%
сива приводит даже к ухудшению.
2. Пузырьковая сортировка (
BubbleSort
) – определенно наихудший из всех сравниваемых здесь методов. Даже его усовершенствованная версия, шей%
кер%сортировка (
ShakerSort
), все равно хуже, чем методы простых вставок
(
StraightInsertion
) и простого выбора (
StraightSelection
), за исключением патологического случая сортировки уже упорядоченного массива.
3. Быстрая сортировка (
QuickSort
) лучше турнирной (
HeapSort
) на множи%
тель от 2 до 3. Она сортирует обратно упорядоченный массив практически с такой же скоростью, как и просто упорядоченный.
Таблица 2.9.
Таблица 2.9.
Таблица 2.9.
Таблица 2.9.
Таблица 2.9. Время выполнения процедур сортировки для массивов из 256 элементов
Š
‹
Œ
StraightInsertion
0.02 0.82 1.64
BinaryInsertion
0.12 0.70 1.30
StraightSelection
0.94 0.96 1.18
BubbleSort
1.26 2.04 2.80
ShakerSort
0.02 1.66 2.92
ShellSort
0.10 0.24 0.28
HeapSort
0.20 0.20 0.20
QuickSort
0.08 0.12 0.08
NonRecQuickSort
0.08 0.12 0.08
StraightMerge
0.18 0.18 0.18

97
Таблица 2.10.
Таблица 2.10.
Таблица 2.10.
Таблица 2.10.
Таблица 2.10. Время выполнения процедур сортировки для массивов из 2048 элементов
Š
‹
Œ
StraightInsertion
0.22 50.74 103.80
BinaryInsertion
1.16 37.66 76.06
StraightSelection
58.18 58.34 73.46
BubbleSort
80.18 128.84 178.66
ShakerSort
0.16 104.44 187.36
ShellSort
0.80 7.08 12.34
HeapSort
2.32 2.22 2.12
QuickSort
0.72 1.22 0.76
NonRecQuickSort
0.72 1.32 0.80
StraightMerge
1.98 2.06 1.98
2.4. Сортировка последовательностей
2.4.1. Простые слияния
К сожалению, алгоритмы сортировки, представленные в предыдущей главе,
неприменимы, когда объем сортируемых данных таков, что они не помещаются целиком в оперативную память компьютера и хранятся на внешних устройствах последовательного доступа, таких как ленты или диски. В этом случае будем счи%
тать, что данные представлены в виде (последовательного) файла, для которого характерно, что в каждый момент времени непосредственно доступен только один элемент. Это очень сильное ограничение по сравнению с теми возможностями,
которые дают массивы, и здесь нужны другие методы сортировки.
Самый важный метод – сортировка слияниями (для всех вариантов сортиров%
ки слияниями Вирт употребляет родовое наименование Mergesort – прим. перев.).
Слиянием (merging, collating) называют объединение двух (или более) упорядо%
ченных последовательностей в одну, тоже упорядоченную последовательность повторным выбором из доступных в данный момент элементов. Слияние – гораз%
до более простая операция, чем сортировка, и эту операцию используют в каче%
стве вспомогательной в более сложных процедурах сортировки последовательно%
стей. Один из способов сортировки на основе слияний – простая сортировка
слияниями (StraightMerge) – состоит в следующем:
1. Разобьем последовательность на две половины, b
и c
2. Выполним слияние частей b
и c
, комбинируя по одному элементу из b
и c
в упорядоченные пары.
3. Назовем получившуюся последовательность a
, повторим шаги 1 и 2, на этот раз выполняя слияние упорядоченных пар в упорядоченные четверки.
4. Повторим предыдущие шаги, выполняя слияние четверок в восьмерки,
и будем продолжать в том же духе, каждый раз удваивая длину сливаемых
Сортировка последовательностей

Сортировка
98
подпоследовательностей, пока вся последовательность не окажется упоря%
доченной.
Например, рассмотрим следующую последовательность:
44 55 12 42 94 18 06 67
На шаге 1 разбиение последовательности дает две такие последовательности:
44 55 12 42 94 18 06 67
Слияние одиночных элементов (которые представляют собой упорядоченные последовательности длины 1) в упорядоченные пары дает:
44 94 ' 18 55 ' 06 12 ' 42 67
Снова разбивая посередине и выполняя слияние упорядоченных пар, получаем
06 12 44 94 ' 18 42 55 67
Наконец, третья операция разбиения и слияния дает желаемый результат:
06 12 18 42 44 55 67 94
Каждая операция, которая требует однократного прохода по всему набору дан%
ных, называется фазой (phase), а наименьшая процедура, из повторных вызовов которой состоит сортировка, называется проходом (pass). В приведенном примере сортировка состояла из трех проходов, каждый из которых состоял из фазы разби%
ения и фазы слияния. Чтобы выполнить сортировку, здесь нужны три ленты, по%
этому процедура называется трехленточным слиянием (three%tape merge).
На самом деле фазы разбиения не дают вклада в сортировку в том смысле, что элементы там не переставляются; в этом отношении они непродуктивны, хотя и составляют половину всех операций копирования. Их можно вообще устранить,
объединяя фазы разбиения и слияния. Вместо записи в единственную последова%
тельность результат слияния сразу распределяется на две ленты, которые будут служить источником исходных данных для следующего прохода. В отличие от вышеописанной двухфазной (two%phase) сортировки слиянием, такой метод назы%
вается однофазным (single%phase), или методом сбалансированных слияний
(balanced merge). Он явно более эффективен, так как нужно вдвое меньше опера%
ций копирования; плата за это – необходимость использовать четвертую ленту.
Мы детально разберем процедуру слияния, но сначала будем представлять данные с помощью массивов, только просматривать их будем строго последова%
тельно. Затем мы заменим массивы на последовательности, что позволит срав%
нить две программы и показать сильную зависимость вида программы от используемого представления данных.
Вместо двух последовательностей можно использовать единственный массив,
если считать, что оба его конца равноправны. Вместо того чтобы брать элементы для слияния из двух файлов, можно брать элементы с двух концов массива%источ%
ника. Тогда общий вид объединенной фазы слияния%разбиения можно проил%
люстрировать рис. 2.12. После слияния элементы отправляются в массив%прием%

99
ник с одного или другого конца, причем переключение происходит после каждой упорядоченной пары, получающейся в результате слияния в первом проходе, пос%
ле каждой упорядоченной четверки на втором проходе и т. д., так что будут равно%
мерно заполняться обе последовательности, представленные двумя концами единственного массива%приемника. После каждого прохода два массива меняют%
ся ролями, источник становится приемником и наоборот.
Дальнейшее упрощение программы получается, если объединить два концеп%
туально разных массива в единственный массив двойного размера. Тогда данные будут представлены так:
a: ARRAY 2*n OF
Индексы i
и j
будут обозначать два элемента из массива%источника, а k
и
L
– две позиции в массиве%приемнике (см. рис. 2.12). Исходные данные – это, конечно,
элементы a
0
... a n–1
. Очевидно, нужна булевская переменная up
, чтобы управлять направлением потока данных; up будет означать, что в текущем проходе элементы a
0
... a n–1
пересылаются «вверх» в переменные a
n
... a
2n–1
, тогда как
up будет указывать, что a
n
... a
2n–1
пересылаются «вниз» в a
0
... a n–1
. Значение up переклю%
чается перед каждым новым проходом. Наконец, для обозначения длины сливае%
мых подпоследовательностей вводится переменная p
. Сначала ее значение равно
1, а затем оно удваивается перед каждым следующим проходом. Чтобы немного упростить дело, предположим, что n
всегда является степенью 2. Тогда первый вариант простой сортировки слияниями приобретает следующий вид:
PROCEDURE StraightMerge;
VAR i, j, k, L, p: INTEGER; up: BOOLEAN;
BEGIN
up := TRUE; p := 1;
REPEAT
;
IF up THEN
i := 0; j := n–1; k := n; L := 2*n–1
ELSE
k := 0; L := n–1; i := n; j := 2*n–1
END;
p- i- j- k- L- ;
up := up; p := 2*p
UNTIL p = n
END StraightMerge
Рис. 2.12. Простая сортировка слияниями с двумя массивами
Сортировка последовательностей

Сортировка
100
На следующем шаге разработки мы должны уточнить инструкции, выделен%
ные курсивом. Очевидно, что проход слияния, обрабатывающий n
элементов, сам является серией слияний подпоследовательностей из p
элементов (
p
наборов).
После каждого такого частичного слияния приемником для подпоследователь%
ности становится попеременно то верхний, то нижний конец массива%приемника,
чтобы обеспечить равномерное распределение в обе принимающие «последова%
тельности». Если элементы после слияния направляются в нижний конец массива%
приемника, то индексом%приемником является k
, и k
увеличивается после каждой пересылки элемента. Если они пересылаются в верхний конец массива%приемни%
ка, то индексом%приемником является
L
, и его значение уменьшается после каж%
дой пересылки. Чтобы упростить получающийся программный код для слияния,
k всегда будет обозначать индекс%приемник, значения переменых k
иa
L
будут об%
мениваться после каждого слияния p
%наборов, а переменная h
, принимающая зна%
чения
1
или
–1
, будет всегда обозначать приращение для k
. Эти проектные реше%
ния приводят к такому уточнению:
h := 1; m := n; (*m = *)
REPEAT
q := p; r := p; m := m – 2*p;
q i- r j- ;
– k, k h;
h := –h;
k L
UNTIL m = 0
На следующем шаге уточнения нужно конкретизировать операцию слияния.
Здесь нужно помнить, что остаток той последовательности, которая осталась не%
пустой после слияния, должен быть присоединен к выходной последовательности простым копированием.
WHILE (q > 0) & (r > 0) DO
IF a[i] < a[j] THEN
i- k- ;
i k; q := q–1
ELSE
j- k- ;
j k; r := r–1
END
END;
i- ;
j-
Уточнение операций копирования остатков даст практически полную про%
грамму. Прежде чем выписывать ее, избавимся от ограничения, что n
является степенью двойки. На какие части алгоритма это повлияет? Нетрудно понять, что справиться с такой более общей ситуацией проще всего, если как можно дольше действовать старым способом. В данном примере это означает, что нужно продол%
жать сливать p
%наборы до тех пор, пока остатки последовательностей%источников

101
не станут короче p
. Это повлияет только на операторы, в которых устанавливают%
ся значения длины сливаемых последовательностей q
и r
. Три оператора q := p; r := p; m := m –2*p нужно заменить на приведенные ниже четыре оператора, которые, как читатель может убедиться, в точности реализуют описанную стратегию; заметим, что m
обозначает полное число элементов в двух последовательностях%источниках, ко%
торые еще предстоит слить:
IF m >= p THEN q := p ELSE q := m END;
m := m–q;
IF m >= p THEN r := p ELSE r := m END;
m := m–r
Кроме того, чтобы обеспечить завершение программы, нужно заменить усло%
вие p = n
, которое управляет внешним циклом, на p
≥
n
. После этих изменений весь алгоритм можно выразить в виде процедуры, работающей с глобальным мас%
сивом из
2n элементов:
PROCEDURE StraightMerge;
(* ADruS24_MergeSorts *)
VAR i, j, k, L, t: INTEGER; (* a is 0 .. 2*n–1 *)
h, m, p, q, r: INTEGER; up: BOOLEAN;
BEGIN
up := TRUE; p := 1;
REPEAT
h := 1; m := n;
IF up THEN
i := 0; j := n–1; k := n; L := 2*n–1
ELSE
k := 0; L := n–1; i := n; j := 2*n–1
END;
REPEAT (*
i- j- k- *)
IF m >= p THEN q := p ELSE q := m END;
m := m–q;
IF m >= p THEN r := p ELSE r := m END;
m := m–r;
WHILE (q > 0) & (r > 0) DO
IF a[i] < a[j] THEN
a[k] := a[i]; k := k+h; i := i+1; q := q–1
ELSE
a[k] := a[j]; k := k+h; j := j–1; r := r–1
END
END;
WHILE r > 0 DO
a[k] := a[j]; k := k+h; j := j–1; r := r–1
END;
WHILE q > 0 DO
a[k] := a[i]; k := k+h; i := i+1; q := q–1
END;
Сортировка последовательностей

Сортировка
102
h := –h; t := k; k := L; L := t
UNTIL m = 0;
up := up; p := 2*p
UNTIL p >= n;
IF up THEN
FOR i := 0 TO n–1 DO a[i] := a[i+n] END
END
END StraightMerge

1   ...   5   6   7   8   9   10   11   12   ...   22

Анализ простой сортировки слияниями. Поскольку p
удваивается на каждом проходе, а сортировка прекращается, как только p > n
, то будет выполнено
⎡log(n)⎤
проходов. По определению, на каждом проходе все n
элементов копируются в точ%
ности один раз. Следовательно, полное число пересылок в точности равно
M = n
× ⎡log(n)⎤
Число сравнений ключей
C
даже меньше, чем
M
, так как при копировании остатков никаких сравнений не требуется. Однако поскольку сортировка слия%
ниями обычно применяется при работе с внешними устройствами хранения дан%
ных, вычислительные затраты на выполнение пересылок нередко превосходят затраты на сравнения на несколько порядков величины. Поэтому детальный ана%
лиз числа сравнений не имеет практического интереса.
Очевидно, сортировка
StraightMerge выглядит неплохо даже в сравнении с эффективными методами сортировки, обсуждавшимися в предыдущей главе.
Однако накладные расходы на манипуляции с индексами здесь довольно велики,
а решающий недостаток – это необходимость иметь достаточно памяти для хране%
ния
2n элементов. По этой причине сортировку слияниями редко применяют для массивов, то есть для данных, размещенных в оперативной памяти. Получить представление о реальном поведении алгоритма
StraightMerge можно по числам в последней строке табл. 2.9. Видно, что
StraightMerge ведет себя лучше, чем
HeapSort
, но хуже, чем
QuickSort
2.4.2. Естественные слияния
Если применяются простые слияния, то никакого выигрыша не получается в том случае, когда исходные данные частично упорядочены. Длина всех сливаемых подпоследовательностей на k
%м проходе не превосходит
2k
, даже если есть более длинные, уже упорядоченные подпоследовательности, готовые к слияниям. Ведь любые две упорядоченные подпоследовательности длины m
и n
можно сразу слить в одну последовательность из m+n элементов. Сортировка слияниями,
в которой в любой момент времени сливаются максимально длинные последова%
тельности, называется сортировкой естественными слияниями.
Упорядоченную подпоследовательность часто называют строкой (string). Но так как еще чаще это слово используют для последовательностей литер, мы вслед за Кнутом будем использовать термин серия (run) для обозначения упорядочен%
ных подпоследовательностей. Подпоследовательность a
i
... a j
,
такую, что
(a i–1
> a i
) & (A
A
A
A
Ak: i
≤ k < j : a k
≤ a k+1
) & (a j
> a j+1
)

103
будем называть максимальной серией, или, для краткости, просто серией. Итак,
в сортировке естественными слияниями сливаются (максимальные) серии вмес%
то последовательностей фиксированной предопределенной длины. Серии имеют то свойство, что если сливаются две последовательности по n
серий каждая, то получается последовательность, состоящая в точности из n
серий. Поэтому пол%
ное число серий уменьшается вдвое за каждый проход, и необходимое число пере%
сылок элементов даже в худшем случае равно n*log(n)
, а в среднем еще меньше.
Однако среднее число сравнений гораздо больше, так как, кроме сравнений при выборе элементов, нужны еще сравнения следующих друг за другом элементов каждого файла, чтобы определить конец каждой серии.
Наше очередное упражнение в программировании посвящено разработке ал%
горитма сортировки естественными слияниями в той же пошаговой манере, кото%
рая использовалась при объяснении простой сортировки слияниями. Вместо мас%
сива здесь используются последовательности (представленные файлами, см.
раздел 1.7), а в итоге получится несбалансированная двухфазная трехленточная сортировка слияниями. Будем предполагать, что исходная последовательность элементов представлена файловой переменной c
. (Естественно, в реальной ситуа%
ции исходные данные сначала из соображений безопасности копируются из неко%
торого источника в c
.) При этом a
и b
– две вспомогательные файловые перемен%
ные. Каждый проход состоит из фазы распределения, когда серии из c
равномерно распределяются в a
и b
, и фазы слияния, когда серии из a
и b
сливаются в c. Этот процесс показан на рис. 2.13.
Рис. 2.13. Фазы сортировки и проходы
Пример в табл. 2.11 показывает файл c
в исходном состоянии (строка 1) и пос%
ле каждого прохода (строки 2–4) при сортировке этим методом двадцати чисел.
Заметим, что понадобились только три прохода. Сортировка прекращается, как только в c
остается одна серия. (Предполагается, что исходная последователь%
ность содержит по крайней мере одну непустую серию.) Поэтому пусть перемен%
ная
L
подсчитывает число серий, записанных в c
. Используя тип
Rider
(«бегу%
Сортировка последовательностей

Сортировка
104
нок»), определенный в разделе 1.7.1, можно сформулировать программу следую%
щим образом:
VAR L: INTEGER;
r0, r1, r2: Files.Rider; (*. 1.7.1*)
REPEAT
Files.Set(r0, a, 0); Files.Set(r1, b, 0); Files.Set(r2, c, 0);
distribute(r2, r0, r1); (*c a b*)
Files.Set(r0, a, 0); Files.Set(r1, b, 0); Files.Set(r2, c, 0);
L := 0;
merge(r0, r1, r2) (*a b c*)
UNTIL L = 1
Таблица 2.11.
Таблица 2.11.
Таблица 2.11.
Таблица 2.11.
Таблица 2.11. Пример сортировки естественными слияниями
17 31' 05 59' 13 41 43 67' 11 23 29 47' 03 07 71' 02 19 57' 37 61 05 17 31 59' 11 13 23 29 41 43 47 67' 02 03 07 19 57 71' 37 61 05 11 13 17 23 29 31 41 43 47 59 67' 02 03 07 19 37 57 61 71 02 03 05 07 11 13 17 19 23 29 31 37 41 43 47 57 59 61 67 71
Двум фазам в точности соответствуют два разных оператора. Их нужно теперь уточнить, то есть выразить с большей детализацией. Уточненные описания шагов distribute
(распределить из бегунка r2
в бегунки r0
и r1
) и merge
(слить из бегун%
ков r0
и r1
в r2
) приводятся ниже:
REPEAT
copyrun(r2, r0);
IF r2.eof THEN copyrun(r2, r1) END
UNTIL r2.eof
REPEAT
mergerun(r0, r1, r2); INC(L)
UNTIL r1.eof;
IF r0.eof THEN
copyrun(r0, r2); INC(L)
END
По построению этот способ приводит либо к одинаковому числу серий в a
и b
,
либо последовательность a
будет содержать одну лишнюю серию по сравнению с файлом b
. Поскольку сливаются соответствующие пары серий, эта лишняя се%
рия может остаться только в файле a
, и тогда ее нужно просто скопировать. Опе%
рации merge и distribute формулируются в терминах уточняемой ниже операции mergerun
(слить серии) и вспомогательной процедуры copyrun
(копировать се%
рию), смысл которых очевиден. При попытке реализовать все это возникает серь%
езная трудность: чтобы определить конец серии, нужно сравнивать два последо%
вательных ключа. Однако файлы устроены так, что каждый раз доступен только один элемент. Очевидно, здесь нужно «заглядывать вперед» на один элемент, по%

105
этому для каждой последовательности заводится буфер, который и должен содер%
жать очередной элемент, стоящий в последовательности за текущим, и который представляет собой нечто вроде окошка, скользящего по файлу.
Уже можно было бы выписать все детали этого механизма в виде полной про%
граммы, но мы введем еще один уровень абстракции. Этот уровень представлен новым модулем
Runs
. Его можно рассматривать как расширение модуля
Files из раздела 1.7, и в нем вводится новый тип
Rider
(«бегунок»), который можно рас%
сматривать как расширение типа
Files.Rider
. С этим новым типом не только мож%
но будет выполнять все операции, предусмотренные для старого типа
Rider
, а так%
же определять конец файла, но и узнавать о конце серии, а также «видеть» первый элемент в еще не прочитанной части файла. Этот новый тип вместе со своими опе%
рациями представлен в следующем определении:
DEFINITION Runs;
(* ADruS242_Runs *)
IMPORT Files, Texts;
TYPE Rider = RECORD (Files.Rider) first: INTEGER; eor: BOOLEAN END;
PROCEDURE OpenRandomSeq (f: Files.File; length, seed: INTEGER);
PROCEDURE Set (VAR r: Rider; VAR f: Files.File);
PROCEDURE copy (VAR source, destination: Rider);
PROCEDURE ListSeq (VAR W: Texts.Writer; f: Files.File);
END Runs.
Выбор процедур требует некоторых пояснений. Алгоритмы сортировки, обсуж%
даемые здесь и в дальнейшем, основаны на копировании элементов из одного файла в другой. Поэтому процедура copy замещает отдельные операции read и write
Для удобства тестирования в последующих примерах мы дополнительно вве%
ли процедуру
ListSeq
, которая печатает файл целых чисел в текст. Кроме того, для удобства введена еще одна процедура:
OpenRandomSeq создает файл с числами в случайном порядке. Эти две процедуры будут служить для проверки обсуждае%
мых ниже алгоритмов. Значения полей eof и eor являются результатами операции copy аналогично тому, как ранее eof был результатом операции read
MODULE Runs;
(* ADruS242_Runs *)
IMPORT Files, Texts;
TYPE Rider*
Rider*
Rider*
Rider*
Rider* = RECORD (Files.Rider) first first first first first: INTEGER; eor eor eor eor eor: BOOLEAN END;
PROCEDURE OpenRandomSeq*
OpenRandomSeq*
OpenRandomSeq*
OpenRandomSeq*
OpenRandomSeq* (f: Files.File; length, seed: INTEGER);
VAR i: INTEGER; w: Files.Rider;
BEGIN
Files.Set(w, f, 0);
FOR i := 0 TO length–1 DO
Files.WriteInt(w, seed); seed := (31*seed) MOD 997 + 5
END;
Files.Close(f)
END OpenRandomSeq;
PROCEDURE Set*
Set*
Set*
Set*
Set* (VAR r: Rider; f: Files.File);
BEGIN
Сортировка последовательностей

Сортировка
106
Files.Set(r, f, 0); Files.ReadInt (r, r.first); r.eor := r.eof
END Set;
PROCEDURE copy* copy* copy* copy* copy* (VAR src, dest: Rider);
BEGIN
dest.first := src.first;
Files.WriteInt(dest, dest.first); Files.ReadInt(src, src.first);
src.eor := src.eof OR (src.first < dest.first)
END copy;
PROCEDURE ListSeq*
ListSeq*
ListSeq*
ListSeq*
ListSeq* (VAR W: Texts.Writer; f: Files.File;);
VAR x, y, k, n: INTEGER; r: Files.Rider;
BEGIN
k := 0; n := 0;
Files.Set(r, f, 0); Files.ReadInt(r, x);
WHILE r.eof DO
Texts.WriteInt(W, x, 6); INC(k); Files.ReadInt(r, y);
IF y < x THEN (* *) Texts.Write(W, "|"); INC(n) END;
x := y
END;
Texts.Write(W, "$"); Texts.WriteInt(W, k, 5); Texts.WriteInt(W, n, 5);
Texts.WriteLn(W)
END ListSeq;
END Runs.
Вернемся теперь к процессу постепенного уточнения алгоритма сортировки естественными слияниями. Процедуры copyrun и merge уже можно выразить явно, как показано ниже. Отметим, что мы обращаемся к последовательностям
(файлам) опосредованно, с помощью присоединенных к ним бегунков. Отметим кстати, что у бегунка поле first содержит следующий ключ в читаемой последова%
тельности и последний ключ в записываемой последовательности.
PROCEDURE copyrun (VAR x, y: Runs.Rider); (* *)
BEGIN (* x y*)
REPEAT Runs.copy(x, y) UNTIL x.eor
END copyrun
(*merge: r0 r1 r2*)
REPEAT
IF r0.first < r1.first THEN
Runs.copy(r0, r2);
IF r0.eor THEN copyrun(r1, r2) END
ELSE Runs.copy(r1, r2);
IF r1.eor THEN copyrun(r0, r2) END
END
UNTIL r0.eor OR r1.eor
Процесс сравнения и выбора ключей при слиянии пары серий прекращается,
как только одна из серий исчерпывается. После этого остаток серии (которая еще не исчерпана) должен быть просто скопирован в серию%результат. Это делается посредством вызова процедуры copyrun

107
По идее, здесь процедура разработки должна завершиться. Увы, вниматель%
ный читатель заметит, что получившаяся программа не верна. Программа некор%
ректна в том смысле, что в некоторых случаях она сортирует неправильно. Напри%
мер, рассмотрим следующую последовательность входных данных:
03 02 05 11 07 13 19 17 23 31 29 37 43 41 47 59 57 61 71 67
Распределяя последовательные серии попеременно в a
и b
, получим a = 03 ' 07 13 19 ' 29 37 43 ' 57 61 71'
b = 02 05 11 ' 17 23 31 ' 41 47 59 ' 67
Эти последовательности легко сливаются в единственную серию, после чего сортировка успешно завершается. Хотя этот пример не приводит к ошибке, он пока%
зывает, что простое распределение серий в несколько файлов может приводить к меньшему числу серий на выходе, чем было серий на входе. Это происходит пото%
му, что первый элемент серии номер i+2
может быть больше, чем последний эле%
мент серии номер i
, и тогда две серии автоматически «слипаются» в одну серию.
Хотя предполагается, что процедура distribute запитывает серии в два файла в равном числе, важное следствие состоит в том, что реальное число серий, запи%
санных в a
и b
, может сильно различаться. Но наша процедура слияния сливает только пары серий и прекращает работу, как только прочитан файл b
, так что ос%
таток одной из последовательностей теряется. Рассмотрим следующие входные данные, которые сортируются (и обрываются) за два последовательных прохода:
Таблица 2.12.
Таблица 2.12.
Таблица 2.12.
Таблица 2.12.
Таблица 2.12. Неправильный результат алгоритма
MergeSort
17 19 13 57 23 29 11 59 31 37 07 61 41 43 05 67 47 71 02 03 13 17 19 23 29 31 37 41 43 47 57 71 11 59 11 13 17 19 23 29 31 37 41 43 47 57 59 71
Такая ошибка достаточно типична в программировании. Она вызвана тем, что осталась незамеченной одна из ситуаций, которые могут возникнуть после выпол%
нения простой, казалось бы, операции. Ошибка типична также в том отношении,
что ее можно исправить несколькими способами и нужно выбрать один. Обычно есть две возможности, которые отличаются в одном принципиальном отношении:
1. Мы признаем, что операция распределения запрограммирована неправиль%
но и не удовлетворяет требованию, чтобы число серий отличалось не боль%
ше, чем на единицу. При этом мы сохраняем первоначальную схему про%
граммы и исправляем неправильную процедуру.
2. Мы обнаруживаем, что исправление неправильной процедуры будет иметь далеко идущие последствия, и тогда пытаемся так изменить другие части программы, чтобы они правильно работали с данным вариантом процедуры.
В общем случае первый путь кажется более безопасным, ясным и честным, обес%
печивая определенную устойчивость к последствиям незамеченных, тонких побоч%
ных эффектов. Поэтому обычно рекомендуется именно этот способ решения.
Сортировка последовательностей

Сортировка
108
Однако не всегда следует игнорировать и второй путь. Именно поэтому мы хотим показать решение, основанное на изменении процедуры слияния, а не про%
цедуры распределения, из%за которой, в сущности, и возникла проблема. Подразу%
мевается, что мы не будем трогать схему распределения, но откажемся от условия,
что серии должны распределяться равномерно. Это может понизить эффек%
тивность. Но поведение в худшем случае не изменится, а случай сильно неравно%
мерного распределения статистически очень маловероятен. Поэтому соображе%
ния эффективности не являются серьезным аргументом против такого решения.
Если мы отказались от условия равномерного распределения серий, то про%
цедура слияния должна измениться так, чтобы по достижении конца одного из файлов копировался весь остаток другого файла, а не только одна серия. Такое изменение оказывается очень простым по сравнению с любыми исправлениями в схеме распределения. (Читателю предлагается убедиться в справедливости это%
го утверждения.) Новая версия алгоритма слияний дана ниже в виде процедуры%
функции:
PROCEDURE copyrun (VAR x, y: Runs.Rider);
(* ADruS24_MergeSorts *)
(* *)
BEGIN (* x y*)
REPEAT Runs.copy(x, y) UNTIL x.eor
END copyrun;
PROCEDURE NaturalMerge (src: Files.File): Files.File; (* *)
VAR L: INTEGER; (* *)
f0, f1, f2: Files.File;
r0, r1, r2: Runs.Rider;
BEGIN
Runs.Set(r2, src);
REPEAT
f0 := Files.New("test0"); Files.Set(r0, f0, 0);
f1 := Files.New("test1"); Files.Set (r1, f1, 0);
(* r2 r0 r1*)
REPEAT
copyrun(r2, r0);
IF r2.eof THEN copyrun(r2, r1) END
UNTIL r2.eof;
Runs.Set(r0, f0); Runs.Set(r1, f1);
f2 := Files.New(""); Files.Set(r2, f2, 0);
(*merge: r0 r1 r2*)
L := 0;
REPEAT
REPEAT
IF r0.first < r1.first THEN
Runs.copy(r0, r2);
IF r0.eor THEN copyrun(r1, r2) END
ELSE
Runs.copy(r1, r2);

109
IF r1.eor THEN copyrun(r0, r2) END
END
UNTIL r0.eor & r1.eor;
INC(L)
UNTIL r0.eof OR r1.eof;
WHILE r0.eof DO copyrun(r0, r2); INC(L) END;
WHILE r1.eof DO copyrun(r1, r2); INC(L) END;
Runs.Set(r2, f2)
UNTIL L = 1;
RETURN f2
END NaturalMerge;
2.4.3. Сбалансированные многопутевые слияния
Затраты на последовательную сортировку пропорциональны необходимому чис%
лу проходов, так как на каждом проходе по определению копируется весь набор данных. Один из способов уменьшить это число состоит в том, чтобы исполь%
зовать больше двух файлов для распределения серий. Если сливать r
серий, кото%
рые равномерно распределены по
N
файлам, то получится последовательность r/N
серий. После второго прохода их число уменьшится до r/N
2
, после третьего –
до r/N
3
, а после k
проходов останется r/N
k серий. Поэтому полное число проходов,
необходимых для сортировки n
элементов с помощью
N
%путевого слияния, равно k = log
N
(n)
. Поскольку каждый проход требует n
операций копирования, полное число операций копирования в худшем случае равно
M = n
×
log
N
(n)
В качестве следующего упражнения в программировании мы разработаем про%
грамму сортировки, основанную на многопутевых слияниях. Чтобы подчеркнуть отличие этой программы от приведенной выше программы естественных двух%
фазных слияний, мы сформулируем многопутевое слияние в виде однофазного сбалансированного слияния. Это подразумевает, что на каждом проходе есть рав%
ное число файлов%источников и файлов%приемников, в которые серии распре%
деляются по очереди. Если используется
2N
файлов, то говорят, что алгоритм ос%
нован на
N
%путевом слиянии. Следуя принятой ранее стратегии, мы не будем беспокоиться об отслеживании слияния двух последовательных серий, попавших в один файл. Поэтому нам нужно спроектировать программу слияния, не делая предположения о строго равном числе серий в файлах%источниках.
Здесь мы впервые встречаем ситуацию, когда естественно возникает структу%
ра данных, представляющая собой массив файлов. На самом деле удивительно,
насколько сильно наша следующая программа отличается от предыдущей из%за перехода от двухпутевых к многопутевым слияниям. Главная причина этого –
в том, что процесс слияния теперь не может просто остановиться после исчерпа%
ния одной из серий%источников. Вместо этого нужно сохранить список еще актив%
ных, то есть до конца не исчерпанных, файлов%источников. Другое усложнение возникает из%за необходимости менять роли файлов%источников и файлов%при%
емников. Здесь становится видно удобство принятого способа косвенного досту%
па к файлам с помощью бегунков. На каждом проходе данные можно копировать
Сортировка последовательностей

Сортировка
110
с одной и той же группы бегунков r
на одну и ту же группу бегунков w
. А в конце каждого прохода нужно просто переключить бегунки r
и w
на другие группы файлов.
Очевидно, для индексирования массива файлов используются номера файлов.
Предположим, что исходный файл представлен параметром src и что для про%
цесса сортировки в наличии имеются
2N
файлов:
f, g: ARRAY N OF Files.File;
r, w: ARRAY N OF Runs.Rider
Тогда можно написать следующий эскизный вариант алгоритма:
PROCEDURE BalancedMerge (src: Files.File): Files.File;
(* *)
VAR i, j: INTEGER;
L: INTEGER; (* *)
R: Runs.Rider;
BEGIN
Runs.Set(R, src); (* R w[0] ... w[N–1]*)
j := 0; L := 0;
# w ! g;
REPEAT
R w[j];
INC(j); INC(L);
IF j = N THEN j := 0 END
UNTIL R.eof;
REPEAT (* r w*)
# r ! g;
L := 0; j := 0; (*j = ! - *)
REPEAT
INC(L);
€# w[j];
IF j < N THEN INC(j) ELSE j := 0 END
UNTIL
;
UNTIL L = 1
(* ! w[0]*)
END BalancedMerge.
Связав бегунок
R
с исходным файлом, займемся уточнением операции первич%
ного распределения серий. Используя определение процедуры copy
, заменим фразу
R w[j]
на следующий оператор:
REPEAT Runs.copy(R, w[j]) UNTIL R.eor
Копирование серии прекращается, когда либо встретится первый элемент сле%
дующей серии, либо будет достигнут конец входного файла.
В реальном алгоритме сортировки нужно уточнить следующие операции:
(1)
# w ! g
;
(2)
€# w j
;

111
(3)
# r ! g;
(4)

Во%первых, нужно аккуратно определить текущие последовательности%источ%
ники. В частности, число активных источников может быть меньше
N
. Очевидно,
источников не может быть больше, чем серий; сортировка прекращается, как только останется единственная последовательность. При этом остается возмож%
ность, что в начале последнего прохода сортировки число серий меньше
N
. Поэто%
му введем переменную, скажем k1
, для обозначения реального числа источников.
Инициализацию переменной k1
включим в операцию
# сле%
дующим образом:
IF L < N THEN k1 := L ELSE k1 := N END;
FOR i := 0 TO k1–1 DO Runs.Set(r[i], g[i]) END
Естественно, в операции (2) нужно уменьшить k1
при исчерпании какого%либо источника. Тогда предикат (4) легко выразить в виде сравнения k1 = 0
. Однако операцию (2) уточнить труднее; она состоит из повторного выбора наименьшего ключа среди имеющихся источников и затем его пересылки по назначению, то есть в текущую последовательность%приемник. Эта операция усложняется необходимостью определять конец каждой серии. Конец серии определяется, ког%
да (a) следующий ключ меньше текущего или (b) досгигнут конец последователь%
ности%источника. В последнем случае источник удаляется уменьшением k1
;
в первом случае серия закрывается исключением последовательности из дальней%
шего процесса выбора элементов, но только до завершения формирования теку%
щей серии%приемника. Из этого видно, что нужна вторая переменная, скажем k2
,
для обозначения числа источников, реально доступных для выбора следующего элемента. Это число сначала устанавливается равным k1
и уменьшается каждый раз, когда серия прерывается по условию (a).
К сожалению, недостаточно ввести только k2
. Нам нужно знать не только количество еще используемых файлов, но и какие именно это файлы. Очевидное решение – ввести массив из булевских элементов, чтобы отмечать такие файлы.
Однако мы выберем другой способ, который приведет к более эффективной про%
цедуре выбора, – ведь эта часть во всем алгоритме повторяется чаще всего. Вместо булевского массива введем косвенную индексацию файлов с помощью отображе%
ния (map) индексов посредством массива, скажем t
. Отображение используется таким образом, что t
0
... t k2–1
являются индексами доступных последовательнос%
тей. Теперь операция (2) может быть сформулирована следующим образом:
k2 := k1;
REPEAT
,
t[m] – , v ;
Runs.copy(r[t[m]], w[j]);
IF r[t[m]].eof THEN

ELSIF r[t[m]].eor THEN
Сортировка последовательностей

Сортировка
112

END
UNTIL k2 = 0
Поскольку число последовательностей на практике довольно мало, для алго%
ритма выбора, который требуется уточнить на следующем шаге, можно приме%
нить простой линейный поиск. Операция

подра%
зумевает уменьшение k1
и k2
, а операция

– уменьшение только k2
,
причем обе операции включают в себя соответствующие перестановки элементов массива t
. Детали показаны в следующей процедуре, которая и является резуль%
татом последнего уточнения. При этом операция
# была рас%
крыта в соответствии с ранее данными объяснениями:
PROCEDURE BalancedMerge (src: Files.File): Files.File; (* ADruS24_MergeSorts *)
(* *)
VAR i, j, m, tx: INTEGER;
L, k1, k2, K1: INTEGER;
min, x: INTEGER;
t: ARRAY N OF INTEGER; (* € *)
R: Runs.Rider; (* *)
f, g: ARRAY N OF Files.File;
r, w: ARRAY N OF Runs.Rider;
BEGIN
Runs.Set(R, src);
FOR i := 0 TO N–1 DO
g[i] := Files.New(""); Files.Set(w[i], g[i], 0)
END;
(* src ! g[0] ... g[N–1]*)
j := 0; L := 0;
REPEAT
REPEAT Runs.copy(R, w[j]) UNTIL R.eor;
INC(L); INC(j);
IF j = N THEN j := 0 END
UNTIL R.eof;
REPEAT
IF L < N THEN k1 := L ELSE k1 := N END;
K1 := k1;
FOR i := 0 TO k1–1 DO (* # - *)
Runs.Set(r[i], g[i])
END;
FOR i := 0 TO k1–1 DO (* # - *)
g[i] := Files.New(""); Files.Set(w[i], g[i], 0)
END;
(* r[0] ... r[k1–1] w[0] ... w[K1–1]*)
FOR i := 0 TO k1–1 DO t[i] := i END;
L := 0; (* *)
j := 0;
REPEAT (* w[j]*)

113
INC(L); k2 := k1;
REPEAT (* v *)
m := 0; min := r[t[0]].first; i := 1;
WHILE i < k2 DO
x := r[t[i]].first;
IF x < min THEN min := x; m := i END;
INC(i)
END;
Runs.copy(r[t[m]], w[j]);
IF r[t[m]].eof THEN (* *)
DEC(k1); DEC(k2);
t[m] := t[k2]; t[k2] := t[k1]
ELSIF r[t[m]].eor THEN (* *)
DEC(k2);
tx := t[m]; t[m] := t[k2]; t[k2] := tx
END
UNTIL k2 = 0;
INC(j);
IF j = K1 THEN j := 0 END
UNTIL k1 = 0
UNTIL L = 1;
RETURN g[0]
END BalancedMerge

1   ...   6   7   8   9   10   11   12   13   ...   22