Таблица 2

СОРТИРОВКА МЕТОДОМ ПРОСТОГО ДВУХПУТЕВОГО слияния

503 I 087 I 512 i 061 908 170 897 275 653 426 154 509 612 \ 677 765 703

503 703 i 512 677 509 908 426 897 653 275 \ 170 154 612 061 \ 765 087

087 503 703 765 154 170 509 908 897 653 426 275 677 612 512 061

061 087 503 512 612 677 703 765 908 897 653 509 426 275 170 154

061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908

сливаемые серии имеют длину 2*, тем не менее никаких явных мер предосторожности на случай таких исключений предусматривать не приходится! (См. упр. 8.) Проверки ступенек вниз в прежнем алгоритме заменены посредством уменьшения переменных q и г и проверки равенства нулю. Благодаря этому время выполнения на машине MIX асимптотически приближается к llTVlgTV машинным циклам, что несколько лучше результата, которого удалось достичь в алгоритме N.

На практике имеет смысл комбинировать алгоритм S с методом простых вставок. Вместо первых четырех просмотров алгоритма S можно методом простых вставок рассортировать группы, скажем, из 16 элементов, исключив таким образом довольно расточительные вспомогательные операции, связанные со слиянием коротких массивов. Как и в случае быстрой сортировки, такое комбинирование методов не влияет на асимптотическое время работы, но дает, тем не менее, немалую выгоду.

Рассмотрим теперь алгоритмы N и S с точки зрения выбора структур данных. Почему необходима память для 27V, а не для N записей? Причина относительно проста: мы работаем с четырьмя списками переменного размера (два входных списка и два выходных списка в каждом просмотре); при этом для каждой пары последовательно распределенных списков используется стандартное понятие "совместный рост" обсуждавшееся в разделе 2.2.2. Но в любой момент времени половина памяти не используется, и после некоторого размышления становится ясно, что в действительности для наших четырех списков следовало бы воспользоваться связным распределением памяти. Если к каждой из N записей добавить поле связи, то все необходимое можно проделать, пользуясь алгоритмами слияния, которые выполняют простые манипуляции связями и совсем не перемещают сами записи. Добавление Л полей связи, как правило, выгоднее добавления пространства памяти еще для N записей; отказавшись от перемещения записей, можно сэкономить и время. Итак, рассмотрим следующий алгоритм.

Алгоритм L {Сортировка посредством слияния списков). Предполагается, что в записяхЛ!,..., Rn содержатся ключи Ki,..., и поля связи Li,..., Ьдг, в которых могут храниться числа от -{N + 1) до {N + 1). В начале и в конце массива имеются искусственные записи Lq и L+i с полями связи Ro и Ллг+х- Этот алгоритм сортировки списков устанавливает поля связи таким образом, что записи оказываются связанными в порядке возрастания. После завершения сортировки Lq указывает на запись с наименьшим ключом; при 1 < к < N связь Lk указывает на запись, следующую за Rk, или Lk - О, если R - запись с наибольшим ключом (см. формулы 5.2.1-(13)).

в процессе работы этого алгоритма записи Ro и Rn+i выполняют роли головных элементов двух линейных списков, подсписки которых в данный момент сливаются. Отрицательная связь означает конец подсписка, о котором известно, что он упорядочен; нулевая связь означает конец всего списка. Предполагается, что N >2.

Через "\Ls\ <- р" обозначена операция "Присвоить Ls значение р или -р, сохранив прежний знак Lg" Такая операция легко реализуется на компьютере MIX, но, к сожалению, не на большинстве других моделей компьютеров. Нетрудно изменить алгоритм, чтобы получить столь же эффективный метод для большинства других машин.

L1. [Подготовить два списка.] Установить Lo <- 1, L+i <~ 2, Li <--(г + 2) при

1 < г < ЛГ - 2 и Ln-i <~ Ln <~ 0. (Созданы два списка, содержащих записи RijRsjRb,... и R2, R4,Re, соответственно; отрицательные связи указывают, что каждый упорядоченный подсписок состоит всего лишь из одного элемента. Другой способ выполнения этого шага, если принять во внимание упорядоченность, которая могла присутствовать в исходных данных, рассмотрен в упр. 12.)

L2. [Начать новый просмотр.] Установить s 4-0, t <- N + 1, р <- Ls, q <- Lt- Если g = О, выполнение алгоритма завершается. (В процессе каждого просмотра р и q "пробегают" по спискам, которые подвергаются слиянию; s обычно указывает на последнюю обработанную запись текущего подсписка, at - на конец только что выведенного подсписка.)

L3. [Сравнение Кр: Kg.] Если Кр > Kg, перейти к шагу L6.

L4. [Продвинуть р.] Установить \Ls\ <~ р, s р, р <~ Lp. Если р > О, вернуться к шагу L3.

L5. [Завершить подсписок.] Установить La <- q, s <- t. Далее установить t <r- q и q <~ Lg один или более раз, пока не станет g < О, после чего перейти к шагу L8.

L6. [Продвинуть q.] (Шаги L6 и L7 двойственны шагам L4 и L5.) Установить jLgj q, S <~ q, q <- Lg. Если q> О, вернуться к шагу L3.

L7. [Завершить подсписок.] Установить La <- р, s <- t. Затем установить f •«- р и р <г- Lp один или более раз, пока не станет р <0.

L8. [Конец просмотра?] (К этому моменту р < О п q < О, так как оба указателя продвинулись до конца соответствующих подсписков.) Установить р <- -р,

q <--q. Если q = О, установить \Lg\ <- р, \Lt\ О и вернуться к шагу L2. В

противном случае вернуться к шагу L3.

Пример работы этого алгоритма приведен в табл. 3, в которой показаны связи к моменту выполнения шага L2. По окончании выполнения алгоритма можно, пользуясь методом из упр. 5.2-12, перекомпоновать в памяти записи Ri,...,Rn так, чтобы их ключи стали упорядоченными. Нужно отметить интересную аналогию между слиянием списков и сложением разреженных многочленов (см. алгоритм 2.2.4А).

Напишем теперь MIX-программу для алгоритма L, чтобы выяснить, столь ли выгодно оперировать списками с точки зрения скорости выполнения, как и с точки зрения расхода памяти?

Программа L (Сортировка посредством слияния списков). Для удобства предполагается, что записи занимают одно слово, причем Lj хранится в поле (0:2) и

Таблица 3

СОРТИРОВКА ПОСРЕДСТВОМ СЛИЯНИЯ СПИСКОВ