T = 3

T = 5

T = 6

T = 8 7-= 10

1 2 5 10 20 50 100 200 500 1000 2000 5000

Начальные серии, .У

Рис. 70. Эффективность многофазного слияния, использующего алгоритм D.

На рис. 71, (а) изображаются снизу вверх А, В, С, D, Е5 и демонстрируется, каким образом числа слияний для каждой серии появляются на ленте. Заметим, что серия в начале любой ленты будет обрабатываться 5 раз, в то время как серия в конце Т1 будет обрабатываться лишь однажды. Эта "дискриминация" при многофазном слиянии приводит к тому, что фиктивные серии лучше помещать в начало ленты, а не в конец. На рис. 71, (Ь) представлен оптимальный порядок распределения серий для пятиуровневого многофазного слияния; каждая новая серия помещается в позицию с наименьшим из оставшихся числом слияний. Заметим, что алгоритм D (см. рис. 69) несколько хуже, так как он заполняет некоторые позиции "4" до того, как будут заполнены все позиции "3".

Рекуррентные соотношения (8) показывают, что все В„, С„, £)„ и являются начальными подцепочками А„. В действительности, используя (8), можно вывести формулы

Еп = (A„ i) + 1,

Dn = (An-iAn-2) + 1,

Cn = (A„ iA„ 2a„ 3) + 1,

Bn = (An-lAn-2An-3An-4) + 1,

An = (A„ iA„ 2a„ 3„ 4a„ 5) + 1,

Начало ленты

Рис. 71. Анализ многофазного распределения пятого уровня на шести лентах: (а) - числа слияний; (Ь) - оптимальный порядок распределения.

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

Ап = п- Q„, (10)

где Qn - цепочка из а„ значений, определяемая законом

Qn = Qn-i{Qn-2 + l)(Qn-3 + 2)(Q„-4 + 3)(Q„-5 + 4) при n > 1;

Qo = 0; Qn = (пустая цепочка) при n < 0. (11)

Так как Q„ начинается с Qn-i, можно рассмотреть бесконечную цепочку Qoo, первые а„ элементов которой совпадают с Q„. Эта цепочка Qoo, по существу, описывает все числа слияний в многофазном распределении. В случае шести лент имеем

Qoo = 011212231223233412232334233434412232334233434452334344534454512232 • • •. (12) В упр. И содержится интересная интерпретация этой цепочки.

При условии, что An есть цепочки mim2...ma„, обозначим через Ап{х) =

г "11

+ х"*»" соответствующую производящую функцию, описываюшую, сколько раз появляется каждое число слияний; аналогично введем В„{х), С„{х), Оп(х), Еп{х). Например, Ai{x) = х*+х+х+х+хЧхЧхЧх = хЧЗхЧЗхЧх. В силу соотношений (9) при п > 1 имеем

En{x) = x{An-i{x)),

Dnix) = x{An-i{x) + An-2(X)),

Сп(х) = x{An-i(x) + An-2(x) + А„ з(х)), (13)

Вп{х) = x{An-iix) + An-2{X) + А„ з(х) + A„ 4(x)),

An(x) = x{An-i{x) + An-2{x) + А„ з(х) + An-4(X) + An-bix)),

где Ao{x) = 1 и An{x) = 0 при n = -1, -2, -3, -4. Следовательно,

п>0 fc>0

Рассматривая серии на всех лентах, положим

Г„(х) = A„(x) + B„(x) + C„(x) + D„(x) + £;„(x), п>1; (15)

из (13) немедленно получаем

Г„(х) = 5A„ i(x) + 4А„ 2(х) + ЗА„ з(х) + 2А„ 4(х) + А„ 5(х), а значит, и

т.тлФТ-У:к11 (16)

4 1 - х(г + г2 + +2* + г)

Соотношение (16) показывает, что можно легко вычислить коэффициенты Т„(х).

(17)

Столбцы этой таблицы дают Г„(х); например, Г4(х) = 2х + 12x2 .з 5,4 Каждый элемент данной таблицы (кроме элементов первой строки) является суммой пяти элементов, расположенных в предыдущей строке непосредственно левее него.

Число серий в "точном" распределении п-го уровня равно Г„(1), а общее количество обрабатываемых серий в процессе их слияния равно производной Т(1). Далее,

полагая х = 1 в (16) и (18), получаем, что число слияний для точного распределения п-го уровня есть коэффициент при г" в a{z)t{z); см. (7). Это согласуется с нашими предыдущими рассуждениями.

Функции Т„(х) можно использовать для определения объема работы, когда фиктивные серии добавляются оптимальным образом. Пусть Е„(т) есть сумма наименьших т чисел слияний в распределении п-го уровня. Посмотрев на столбцы (17), мы без труда вычислим эти суммы Е„(т).

m = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

п = 1 12 3 4 5 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

п = 2 1234 6 8 10 12 14 ОООООООООООООООООООООООО

п = 3 1 2 3 5 7 9 И 13 15 17 19 21 24 27 30 33 36 оо оо оо оо

п = 4 1 2 4 6 8 10 12 14 16 18 20 22 24 26 29 32 35 38 41 44 47 (19)

п = Ъ 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 32 35 38 41 44 47

п = 6 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 33 36 39 42 45 48

п = 7 2 4 6 8 10 12 14 16 18 20 23 26 29 32 35 38 41 44 47 50 53

Например, для сортировки 17 серий с помощью распределения 3-го уровня общее

количество операций составит Из (17) = 36. Но, если использовать распределение