Сбалансированная Каскадная Многофазная

(Т=4, S=8) (Т=4, S=14) (Т=3, S=13)

v = i 4, 4, О, 0) v°> = { 6, 5, 3, 0) 7;(2> = ( 5, 8, 0)

2/() = (+1,+1,-1, 0) 2/("> = (+!,+!,+1,-1) 2/(> = (+1,+1,-1)

2/<«> = (+1,+1, 0,-1) 2/(> =(+1,+1,+1,-1) у(н)=(+1,+1, 1)

2/W = (+l,+l,-l, 0) -(+1,+1,+1,-1) 2/(10)(+1+1 1)

2/(> = (+1,+1, 0,-1) 2/(> =(+1,+1,-1, 0) 2/(«> =(+1,+1,-1)

2/(> = (-1, 0,+1,+1) 2/(«> =(+1,+1,-1, 0) 2/W =(+1,+1,-1)

у(2> = ( 0,-1,+1,+1) 2/(> =(+1,-1, О, 0) =(-1,+1,+1)

2/(> = (+1,+1,-1, 0) 2/W =(-1,+1,+1,+1) !/W =(-1,+1,+1)

2/(> = ( О, О, 1, 0) 2/(> =( 0,-1,+1,+1) 2/W =( 1,+1,+1)

2/(=> =( О, 0,-1,+1) !/W =(+1,-1,+1)

2/(> =(+!,+!,+1,-1) 2/*

уС» =(0, О, О, 1) yW =(+1,+1,-1)

у(> =(-1,+1,+1) 2/" =(1, О, 0)

Может показаться неудобным нумеровать данные векторы с конца так, чтобы у{т) появлялся первым, а у") - последним, но этот нестандартный способ нумерации более удобен при разработке теории. Для поиска оптимального метода неплохо сначала вывести рассортированный результат и представить себе, как его можно распределить на различные ленты (т. е. выполнить операцию, обратную слиянию). Затем следует распределить то, что получилось, и т. д., рассматривая последовательные распределения v°\ и, и),... в порядке, обратном тому, в котором они в действительности появляются в результате слияний в ходе сортировки. Фактически именно этот подход использовался нами при анализе многофазного и каскадного слияний.

Каждая схема слияния, очевидно, имеет векторное представление. И обратно, как легко видеть, последовательность векторов у"*)... i/( соответствует реальной схеме слияния тогда и только тогда, когда выполняются следующие три условия:

i) вектор 1/° является единичным;

ii) ровно одна компонента вектора y равна -1; все остальные компоненты равны О или +1, m > г > 1;

Ш) все компоненты вектора у Н-----h у + у(°) неотрицательны, m > г > 1.

Информацию о схеме слияния можно представить в виде дерева. Мы строим дерево с одним внешним "листовым" узлом для каждой начальной серии и с одним внутренним узлом для каждой серии, полученной в результате слияния. Потомками любого внутреннего узла являются образующие его серии. Каждый внутренний узел помечается номером шага, на котором была образована соответствующая серия, при этом шаги нумеруются в обратном порядке, как в векторном представлении. Кроме того, ребра непосредственно над каждым узлом помечаются именем ленты, на которой находится данная серия. Например, три приведенные выше схемы имеют представления в виде дерева, изображенные на рис. 76, если мы назовем ленты А, В, С, D, а не Т1, Т2, ТЗ, Т4.

Это удобное и наглядное представление многих существенных свойств схемы слияния. Например, если серия на уровне О дерева (корень) должна быть восходящей, то серии на уровне 1 должны быть нисходящими, серии на уровне 2 - восходящими и т. д. Некоторая начальная серия является восходящей тогда и только

Сбалансированная (Г = 4, 5 = 8)

Каскадная (Г = 4, 5 = 14)

Многофазная (Г = 3, 5=13)

Рис. 76. Представления трех схем слияния в виде деревьев.

тогда, когда соответствующий внешний узел находится на уровне с четным номером. Далее, суммарное количество начальных серий, обрабатываемых при слиянии (не включая начальное распределение), в точности равно длине внешнего пути дерева, поскольку каждая начальная серия на уровне к обрабатьшается ровно к раз.

Любая схема слияния имеет представление в виде дерева, но не каждое дерево определяет схему слияния. Дерево, внутренние узлы которого помечены числами от 1 до m и ребра которого помечены именами лент, изображает правильную схему слияния с обратным чтением тогда и только тогда, когда

a) никакие два ребра, смежные с одним внутренним узлом, не имеют одного и того же имени ленты;

b) если i> j п если А есть имя ленты, то дерево не содержит конфигурации

о ф

А п А

® о

Условие (а) очевидно, так как вводные и выводные ленты слияния должны быть различны; условие (Ь) также очевидно. Условие "непересечения" (с) отражает характерное для операций обратного чтения ленты ограничение "последним включается - первым исключается" Серия, обра,зованная на шаге к, должна быть удалена прежде серии, сформированной ранее на той же ленте; следовательно, конфигурации (4) невозможны. Нетрудно проверить, что любое помеченное дерево, удовлетворяющее условиям (а), (Ь) и (с), действительно соответствует некоторой схеме слияния с обратным чтением.

Если имеется Г накопителей на магнитной ленте, то из условия (а) следует, что степень каждого внутреннего узла равна Т - 1 или меньше. Присвоить подходящие метки всем таким деревьям не всегда возможно; например, если Г = 3, то не существует схемы слияния с деревом вида

Такая форма дерева позволила бы найти оптимальную схему слияния, если бы можно было соответствующим образом присвоить номера шагов и номера лент, поскольку это единственное дерево с минимальной длиной внешнего пути среди деревьев, имеющих четыре внешних узла. Но в силу симметрии структуры этого дерева имеется, по существу, только один способ пометить его, соблюдая ус7ювия (а) и (Ь):

Однако при этом нарушается условие (с). Дерево, которое может быть помечено в соответствии с упомянутыми условиями с использованием Т или меньше имен лент, называется T-lifо-деревом. Другой способ охарактеризовать все помеченные деревья, которые могут возникнуть из схемы слияния, состоит в рассмотрении метода "выращивания" всех подобных деревьев. Начнем с некоторого имени ленты, скажем