Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией
 Скачать 2.67 Mb.
|
удваивается на каждом проходе, а сортировка прекращается, как только 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 |