N2. [Подготовка к просмотру.] Если s = О, установить i 1, j <- N, к N + 1, I i- 2N; если s = I, установить i N + 1, j +- 2N, к 1,1 <- N. (Переменные г, j, к, I указывают текущие позиции во "входных массивах" из которых выполняется чтение, и в "выходных массивах" в которые осуществляется запись.) Установить d <- 1, f i- 1. (Переменная d задает текущее направление вывода; / устанавливается равной О, если необходимы дальнейшие просмотры.)

N3. [Сравнение Ki: Kj.] Если Ki > Kj, перейти к шагу N8. Если i = j, установить Rk Ri п перейти к шагу N13.

N4. [Пересылка Л,.] (Шаги N4-N7 аналогичны шагам МЗ-М4 алгоритма М.) Установить Rk <- Ri, к <- к + d.

N5. [Ступенька вниз?] Увеличить i на 1. Далее, если Kii < Ki, вернуться к шагу N3.

N6. [Пересылка Rj.] Установить Rk <- Rj, к <- к + d.

N7. [Ступенька вниз?] Уменьшить j на 1. Далее, если Kj+i < Kj, вернуться к шагу N6; иначе - перейти к шагу N12.

N8. [Пересылка i?j.] (Шаги N8-NИ двойственны шагам N4-N7.) Установить Л<: Rj, к < к + d.

N9. [Ступенька вниз?] Уменьшить j на 1. Далее, если Kj+i < Kj, вернуться к шагу N3.

N10. [Пересылка Ri.] Установить Rk +- Ri, к к + d.

N11. [Ступенька вниз?] Увеличить г на 1. Далее, если Ki-i < Ki, вернуться к шагу N10.

N12. [Переключение направления.] Установить f О, d <--da выполнить замену

к <+ I. Вернуться к шагу N3.

N13. [Переключение областей.] Если / = О, установить s <- 1 - s и вернуться к шагу N2. В противном случае сортировка будет завершена. Если s = О, установить (Ri,. ., Rn) (Rn+i, , R2n)- (Если результат можно оставить в области {Rn+1,. , R2n), примерно в половине случаев последнее копирование оказывается необязательным.)

В этом алгоритме есть одна небольшая тонкость, которая объясняется в упр. 5.

Запрограммировать алгоритм N для машины MIX нетрудно, но можно проанализировать ход его выполнения и без разработки программы. Если массив случаен, то в нем имеется около 7V восходящих серий, так как Ki > Ki+i с вероятностью . Подробная информация о количестве серий при несколько отличных предположениях была получена в разделе 5.1.3. При каждом просмотре (на каждом проходе алгоритма) число серий сокращается вдвое (за исключением необычных случаев, таких, как ситуация, описанная в упр. 6). Следовательно, число просмотров составляет, как правило, около Ig Л = IgTV - 1. При каждом просмотре необходимо переписать все N записей, и, как показано в упр. 2, большая часть времени затрачивается на выполнение шагов N3-N5, N8, N9. Если считать, что равные ключи встречаются с малой вероятностью, то время, затрачиваемое во внутреннем цикле, можно охарактеризовать следующим образом.

N1. Начальная установка

N2. Подготовка к просмотру

КЗ. Сравнение

N4. Пересылка Ri

N5. Ступенька

N6. Пересылка Rj

N7. Ступенька Нет вниз?

N13. Переключение областей

N8. Пересылка Rj

N9. Ступенька

Да

N10. Пересылка Ri 1

N11.

Ступенька

N12. Переключение направления

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

Рис. 30. Сортировка методом слияния.

Либо

Либо

Значит, при каждом просмотре на каждую запись затрачивается 12.5 машинных циклов и общее время выполнения асимптотически приближается к 12.57Vlg7V как в среднем, так и в наихудшем случаях. Это происходит медленнее быстрой сортировки и не настолько лучше времени работы пирамидальной сортировки, чтобы оправдать вдвое больший расход памяти, так как асимптотическое время выполнения программы 5.2.3Н равно ISNlgN.

В алгоритме N границы между сериями полностью определяются ступеньками вниз. Такой подход обладает тем потенциальным преимуществом, что исходные массивы с преобладанием возрастающего или убывающего расположения элементов могут обрабатываться очень быстро, но при этом замедляется основной цикл вычислений. Вместо того чтобы проверять ступеньки вниз, длину серий можно установить принудительно: считать, что все серии исходного массива имеют длину 1, после первого просмотра все серии (кроме, возможно, последней) имеют длину 2,..., после к-го просмотра все серии (кроме, возможно, последней) имеют длину 2*. В отличие от "естественного" слияния в алгоритме N такой способ называется простым двухпутевым слиянием.

Алгоритм простого двухпутевого слияния очень напоминает алгоритм N - он, по существу, описывается той же блок-схемой. Тем не менее методы отличаются один от другого, и поэтому стоит записать весь алгоритм целиком.

Алгоритм S {Сортировка методом простого двухпутевого слияния). Как и в алгоритме N, при сортировке записей i?i,..., Rn используются две области памяти.

51. [Начальная установка.] Установить s О, р 1. (Смысл переменных s, i, j, к, I и d приводится в описании алгоритма N. Здесь р - размер восходящих серий, которые будут сливаться во время текущего просмотра. Другие переменные q и г предназначены для отслеживания количества неслитых элементов в сериях в ходе выполнения алгоритма.)

52. [Подготовка к просмотру.] Если s = О, установить i < 1, j N, к +- N, I i-2N +1; если s = 1, установить г <- N +1, j <- 2N, к i- О, I i- N +1. Далее установить d 1, q р, г р.

53. [Сравнение Кг: Kj.] Если Ki > Kj, перейти к шагу S8.

54. [Пересылка Ri.] Установить к к + d, Rk Rt-

55. [Конец серии?] Установить гг + 1, qq-1. Если q > О, вернуться к шагу S3.

56. [Пересылка Rj.] Установить к <г- k + d. Далее, если к = I, перейти к шагу S13; в противном случае установить Rk Rj.

ST. [Конец серии?] Установить г<-г-1. Если г > О, вернуться к

шагу S6; в противном случае перейти к шагу S12.

58. [Пересылка Rj.] Установить к к + d, Rk Rj-

59. [Конец серии?] Установить гг-1. Если г > О, вернуться к шагу S3.

810. [Пересылка Rj.] Установить к к + d. Далее, если к = 1, перейти к шагу S13; в противном случае установить Rk Ri-

811. [Конец серии?] Установить ii + l, q<-q~l. Если q > О, вернуться к шагу S10.,

S12. [Переключение направления.] Установить q <- р, г <- р, d <--d и выполнить

замену к <+ I. Если j - i < р, вернуться к шагу S10; в противном случае вернуться к шагу S3.

813. [Переключение областей.] Установить р <- р + р. Если р < N, установить s +-1 - S и вернуться к шагу S2. В противном случае сортировка будет завершена. Если 3 = 0, установить

{Ru---,Rn) {Rn+i,---,R2n)-

(Последнее копирование необходимо выполнять тогда и только тогда, когда [IgTV] нечетно, независимо от распределения записей в исходном массиве. Таким образом, можно заранее предсказать положение рассортированного массива и копирование, скорее всего, станет излишним.)

Пример выполнения алгоритма представлен в табл. 2. Довольно удивительно, что этот метод прекрасно работает и тогда, когда N не является степенью 2. Не все