D3. Продвижение j

D4. Подняться на один уровень

Входные данные исчерпаны

D6. Опуститься на одни уровень

Сортировка закончена

Рис. 68. Сортировка методом многофазного слияния.

ТАРЕ [ j], 1 < j <Т: Номер физического накопителя на магнитной ленте, соответствующего логическому устройству с номером j

(Удобно работать с номерами "логических" накопителей на магнитной ленте, соответствие которых физическим накопителям .меняется в процессе выполнения алгоритма.)

D1. [Начальная установка.] Установить A[j] <- D[j] ч- 1 и TAPE[j] ч- j при 1 < j < Т. Установить А [Г] <- В[Г] <- О и ТАРЕ [Г] ч- Т. Затем установить I i- 1,

D2. [Ввод на ленту j.] Записать одну серию на ленту j и уменьшить D[j] на 1.

Затем, если ввод исчерпан, перемотать все ленты и перейти к шагу D5. D3. [Продвижение j.] Если D[j] < D[j-H], то увеличить j на 1 и вернуться к

шагу D2. В противном случае, если D[j] = О, перейти к шагу D4, иначе -

установить j <- 1 и вернуться к шагу D2.

D4. [Подняться на один уровень.] Установить I +-1 + 1, а <- kill, затем для j = I, 2, ..., Р (именно в таком порядке) установить D[j] <- а + klj + Ц - A[j] и A[j] <- а -Ь A[j -ь 1]. (См. (1). Отметим, что А[Р-Ь 1] всегда 0. В этом месте будем иметь D[l] > D[2] > • • > В[Г].) Теперь установить j <- 1 и вернуться к шагу D2.

D5. [Слияние.] Если Z = О, то сортировка завершена и результат находится на ТАРЕ[1]. В противном случае выполнять слияние серий с лент ТАРЕ[1],..., ТАРЕСР] на ТАРЕ [Г] до тех пор, пока ТАРЕ[Р] не станет пустой и D[P] = 0. Процесс слияния для каждой сливаемой серии должен протекать следующим образом. Если D[j] > О для всех j, 1 < j < Р, то увеличить В[Г] на 1 и уменьшить каждое D [j] на 1 для 1 < i < Р; в противном случае выполнять слияние по одной серии с каждой ленты TAPE[j], такой, что D[j] = О, и уменьшить D[j] на 1 для остальных j. (Таким образом, считается, что фиктивные серии находятся в начале ленты, а не в конце.)

Рис. 69. Порядок, в котором серии 34-65 распределяются на ленты при переходе с уровня 4 на уровень 5. (См. таблицу точных распределений (1).) Заштрихованные области соответствуют первым 33 сериям, которые были распределены к моменту достижения уровня 4. Последняя строка в каждой колонке соответствует началу ленты.

Т2 Тз Ti

D6. [Опуститься на Один уровень.] Установить / <-1-1. ПеремоТ{1ть ленты ТАРЕ [Р] и ТАРЕ [Г]. (В действительности перемотка ТАРЕ [Р] могла быть начата на шаге D5, после ввода с нее последнего блока.) Затем установить (ТАРЕ[1], ТАРЕ [2], ...,ТАРЕОТ) (ТАРЕ [Г], ТАРЕ [1],..., ТАРЕ [Г-1]), (D[l], D[2],..., В[Г]) (D [Г], D [1],..., D [Г - 1]) и вернуться к шагу D5.

Правило распределения, которое так лаконично сформулировано на шаге D3 этого алгоритма, стремится по возможности уравнять числа фиктивных серий на каждой ленте. На рис. 69 иллюстрируется распределение серий, когда мы переходим от уровня 4 (33 серии) к уровню 5 (65 серий) в сортировке с шестью лентами; если было бы, скажем, только 53 начальные серии, то все серии с номерами 54 и выше рассматривались бы как фиктивные. (На самом деле серии записываются в конец ленты, но удобнее считать, что они залисываются в начало, так как предполагается, что фиктивные серии находятся в начале ленты.)

Мы уже рассмотрели первые три из поставленных выше вопросов; осталось выяснить чиаю "проходов" по данным. Сравнивая наш "шестиленточный пример" с таблицей (1), мы видим, что суммарное количество обработанных начальных серий при 5 = *б составляет 051-1-04*2 + 033 + 024 + 015 + 006, если исключить начальный проход распределения. В упр. 4 выводятся производящие функции

а(г) = 5: а„." = i , ,2 Да ,4

п>0

5z -f 42 + 3z + 2г* + z

n>l

Отсюда следует, что в общем случае число обрабатываемых начальных серий при S = tn равно коэффициенту при 2" в произведении a(z)t{z) плюс (это дает начальный проход распределения). Теперь вычисляем асимптотическое поведение многофазного слияния, как показано в упр. 5-7, и получаем результаты, приведенные в табл. 1.

В табл. 1 "Относительный рост" есть предел lim„ >oo *n+i/*n, показывающий, во сколько приблизительно раз возрастает число серий на каждом проходе. "Проходы" - это среднее количество обработок каждой записи, а именно - 1/5, умноженное на общее число начальных серий, обрабатываемых в течение фаз распреде-

Таблица 1

аппроксимация поведения сортировки методом многофазного слияния

ления и слияния. Указанные числа проходов и фаз справедливы в каждом случае с точностью до 0(5~) при некотором е > О для точного распределения при 5 оо.

На рис. 70 изображены в виде функций от 5 средние количества слияний каждой записи с помощью алгоритма D для неточных чисел. Заметим, что при использовании трех лент сразу после точных распределений появляются "пики" относительной неэффективности, но это явление в значительной степени исчезает при наличии четырех или более лент. Использование восьми или более лент дает сравнительно малое улучшение по сравнению с шестью или семью лентами.

Более детальный анализ. В сбалансированном слиянии, требующем к проходов, каждая запись обрабатывается в ходе сортировки ровно к раз. Но многофазная процедура не является такой беспристрастной: одни записи могут обрабатываться намного больше раз, чем другие, и можно увеличить скорость, если помещать фиктивные серии в часто обрабатываемые позиции.

По этой причине проанализируем более подробно многофазное распределение. Вместо того чтобы интересоваться только числом серий на каждой ленте, как в (1), присвоим каждой серии число слияний , т. е. определим, сколько раз она будет обрабатываться в течение всего процесса сортировки. Вместо (1) получим следующую таблицу.

Уровень Т1 Т2 ТЗ Т4 Т5

О О - . - - -

11 1 111

2 21 21 21 21 2

3 3221 3221 3221 322 32

4 43323221 43323221 4332322 433232 4332

5 5443433243323221 544343324332322 54434332433232 544343324332 54434332

п An Вп Сп Dn En

n + l {An + l)Bn (An + 1)C„ (An + l)Dn (An + l)En An + 1 (8)

Здесь An - цепочка из a„ значений, представляющих числа слияний каждой серии на Т1, если начать с распределения п-го уровня; Вп - соответствующая цепочка для Т2 и т. д. Обозначение "(А„ + 1)Вп читается так: "А„, все значения которой увеличены на 1, а за ней - В„"