показывающей, что a<b<dMc<d. (Для представления известных отношений порядка между элементами удобно воспользоваться ориентированными графами, такими, что X считается меньше у тогда и только тогда, когда на графе есть путь от з; к у.) Теперь вставляем пятый элемент К5 = е в соответствующее место среди {a,b,d}; для этого требуются всего два сравнения, поскольку можно сравнить его сначала с Ь, а затем - с а или d. Таким образом, остается один из четырех возможных вариантов

Ь d е b d bed b d е

ГУ ГУ rr

и в каждом случае достаточно еще двух сравнений, чтобы вставить с в цепочку остальных элементов, меньших d. Такой способ сортировки пяти элементов впервые обнаружил Г. Б. Демут (Н. В. Demuth) [Ph. D. thesis, Stanford University (1956), 41-43].

Сортировка посредством вставок и слияния. Изящное обобщение изложенного выше метода принадлежит Лестеру Форду (мл.) (Lester Ford, Jr.) и Селмеру М. Джонсону (Selmer М. Johnson). Поскольку оно объединяет некоторые особенности двух способов сортировки (посредством слияний и посредством вставок), мы назовем этот метод сортировкой посредством вставок и слияния. Рассмотрим, например, сортировку 21 эле.мента. Начать можно со сравнений десяти пар ключей К1:К2,Кз:К4,... ,Kig:K2o; затем следует рассортировать посредством вставок и слияния ббльшие элементы пар. В результате получим конфигурацию

01 02 аз «4 as ае ау ag ад аю

ГГГГГГГ7Т7. •

61 62 63 64 65 67 бе 69 610 Ь\\

аналогичную (5). Следующий шаг - вставить элемент 63 в последовательность {61,01,02}, а затем - 62 в последовательность остальных элементов, меньших 02. В результате приходим к конфигурации

С], С2 сз С4 С5 Сб а4 аь ае ау as ад аю

-гтттт. • «)

64 65 6б 67 бе Ьэ 610 Ьи

Назовем верхние элементы главной цепочкой. Элемент 65 можно вставить в главную цепочку за три сравнения (сравнив его сначала с с4, затем с Сг или Се и т. д.). После этого еще за три сравнения можно переместить в главную цепочку 64 и получить

dl d2 ds d4 di de dj dg dg dio ae 0,7 ag ag аю •->•->•->•->•->•-->•->

/. •

6б br bg bg 610 611

"Следующий шаг решающий; ясно ли вам, что делать дальше?" При помощи всего четырех сравнений вставляем Ьц (но не 67) в главную цепочку. Далее элементы Ью, bg, bs, br, Ьб (именно в таком порядке) можно вставить в нужное место в главной цепочке не более чем за четыре сравнения каждый.

Аккуратный подсчет числа требуемых сравнений показывает, что 21 элемент можно рассортировать не более чем за 10--5(10)--2--2--3--3--4+4--4+4+4--4 = 66 шагов. Поскольку

2б5 21! < 2**,

ясно также, что и в любом другом случае необходимо не менее 66 сравнений; следовательно,

5(21) = 66. (10)

(При сортировке с помощью бинарных вставок понадобилось бы 74 сравнения.)

В общем случае сортировка посредством вставок и слияния для п элементов выглядит следующим образом.

i) Сравнить [n/2J непересекающихся пар элементов. (Если п нечетно, то один элемент не участвует в сравнениях.)

ii) Рассортировать [n/2J больших элементов пар, найденных на шаге (i), посредством вставок и слияния.

iii) Для элементов введем обозначения oi, 02,..., a„/2j, 61,62, •. •, Ь\п/2], как в (7), где ai < «2 < < а bi <ai при 1 < i < [п/2]; назовем 61 и все элементы а главной цепочкой. Не трогая элементов bj при j > ln/2], вставим посредством бинарных вставок в главную цепочку остальные элементы b в следующем порядке:

Ьз.Ьг; 65,4; 611,610,..., бе; 6(,6( i,... ,6( j+i; ---- (11)

Наша цель - сформировать последовательность (1,2,3,4,...) = (1,3,5,11, ...), присутствующую в (11), таким образом, чтобы каждый из элементов bt,bt-l, ,6f i+i можно было вставить в главную цепочку не более чем за к сравнений. Обобщая (7)-(9), получим диаграмму

--ГУ-7/

на которой главная цепочка до Of-i включительно содержит 2*; 1 + {tk - tk-i - 1) элементов. Это число должно быть меньше 2*; для нас лучше всего положить его равным 2* - 1, и тогда

tk-i+tk = 2>. (12)

Поскольку ti = 1, для удобства можно положить to = I. В итоге, суммируя члены геометрической прогрессии, найдем

tk=2- tk-i = 2* - 2*-i + tk-2 = • • • = 2* - 2*-i + + (-1)*2"

= (2*+i+ ( i))/3. (13)

(Любопытно, что точно такая же последовательность возникла при изучении алгоритма вычисления наибольшего общего делителя двух целых чисел; см. упр. 4.5.2-36.)

Пусть F{n) - число сравнений, необходимых для сортировки п элементов посредством вставок и слияния. Ясно, что

Г{п) = [п/2} + F{[n/2}) + G{ln/2]), (14)

где функция G описывает объем работы, выполняемой на шаге (iii). Если tk-i < тп < tk, то, суммируя по частям, получаем

G{m) = J2j{tj - tj-i) + fc(m - tk-i) = fcm - (to + ti + • + 4-i)- (15) Положим

Wk=to + h + ---+ tk-i = L2+V3J, (16)

и тогда {WQ,Wi,W2,W3,Wi,...) = (0, 1, 2, 5, 10, 21,...). В упр. 13 показано, что

F(n) - F{n - 1) = fc тогда и только тогда, когда Wk < п < w+i, (17)

а последнее условие эквивалентно неравенствам

- <" -

или fc -1-1 < lg3n < fc + 2; следовательно,

F(n)-F(n-1)= [Igfn]. (18)

(Эта формула получена А. Хадьяном (А. Hadian) [Ph. D. thesis, Univ. of Minnesota (1969), 38-42].) Отсюда вытекает, что функция F{n) выражается на удивление простой формулой

Fin) = \\glk], (19)

которая очень похожа на формулу (3) для метода бинарных вставок. В замкнутом виде эту сумму можно найти в упр. 14.

Воспользовавшись (19), нетрудно построить таблицу значений функции F{n); имеем

п = 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 16 17 [lgn!l= 0 1 3 5 7 10 13 16 19 22 26 29 33 37 41 45 49 F{n) = О 1 3 5 7 10 13 16 19 22 26 30 34 38 42 46 50

п = 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

[Ign!] = 53 57 62 66 70 75 80 84 89 94 98 103 108 113 118 123

F{n) = 54 58 62 66 71 76 81 86 91 96 101 106 111 116 121 126

Обратите внимание на то, что,F{n) = [Ign!] при 1 < п < И и при 20 < п < 21;

таким образом, при этих значениях п сортировка посредством вставок и слияния оптимальна:

S{n) = l\gn\] = F{n) при n = 1, 11, 20 и 21. (20)

Задачу нахождения функции S{n) поставил Гуго Штейнгауз (Hugo Steinhaus) во втором издании своей классической книги Mathematical Snapshots (Oxford University Press, 1950, 38-39)*. Он описал метод бинарных вставок, который является наилучшим способом сортировки п элементов при условии, что п-й элемент не рассматривается до тех пор, пока не рассортированы первые п - 1 элементов; он

* Есть русский перевод первого издания этой книги: Штейнгауз Г. Математический калейдоскоп. - М.: Гостехиздат, 1949. - Прим. перев.