Специальные методы сортировки a

Рис. 11.15. Пример полифазного слияния
Вместо поддержания сбалансированного количества отрезков, как это было на рис. 11.12, здесь на стадии начального распределения на лентах размещается различное количество отрезков в соответствии с заранее определенной схемой. Затем на каждой фазе выполняются трехпутевые слияния, до завершения сортировки. В этом случае число фаз больше, чем для сбалансированного слияния, но эти фазы задействуют не все данные.
Слияние разбивается на множество фаз (не все из них выполняются для всех данных), для которых не нужно дополнительное копирование. На рис. 11.16 показано, как производится расчет отрезков для начального распределения. Количество отрезков на каждом устройстве определяется обратным подсчетом.
В примере, представленном на рис. 11.16, мы рассуждаем следующим образом: нужно закончить слияние с 1 отрезком на устройстве 0. Следовательно, перед последним слиянием устройство 0 должно быть свободным, а на устройствах 1, 2 и 3 должно быть по одному отрезку. Далее мы определяем, каким должно быть распределение отрезков до выполнения предпоследнего слияния, чтобы получить требуемое распределение. Одно из устройств 1, 2 или 3 должно быть пустым (чтобы его можно было использовать в качестве выходного для предпоследнего слияния) - пусть это будет устройство 3. То есть предпоследнее слияние сливает по одному отрезку с каждого из устройств 0, 1 и 2 и записывает результат на устройство 3. Поскольку предпоследнее слияние оставляет 0 отрезков на устройствах 0 и 1, оно должно начаться с одним отрезком на устройстве 0 и двумя отрезками на каждом из устройств 1 и 2. Аналогичные рассуждения приводят нас к заключению, что слияние, предшествующее только что рассмотренному, должно начинаться с 2, 3 и 4 отрезками на устройствах 3, 0 и 1 соответственно. Продолжая в том же духе, можно построить таблицу распределения отрезков: для получения очередного ряда выбираем из следующего за ним ряда максимальное число, заменяем его нулем и добавляем его к каждому из оставшихся чисел. Это соглашение соответствует определению в предыдущем ряду слияния максимального порядка, которое порождает текущий ряд. Такая техника работает с любым количеством устройств (не менее трех). Возникающие при этом числа являются обобщенными числами Фибоначчи, которые обладают множеством интересных свойств. Если количество отрезков не есть обобщенное число Фибоначчи, то вводятся фиктивные отрезки, которые необходимы для заполнения таблицы.
Основная трудность при реализации полифазного слияния состоит в распределении начальных отрезков (см. упражнение 11.54).
Получив распределение отрезков и рассуждая в прямом направлении, можно вычислить относительные размеры отрезков, рассчитывая их после каждого слияния. Например, первое слияние в примере на рис. 11.16 порождает 4 отрезка размером 3 единицы на устройстве 1 и оставляет 2 отрезка размером 1 на устройстве 0 и 1 отрезок размером 1 на устройстве 3 и т.д. Как и в случае сбалансированного многопутевого слияния, можно выполнить указанные операции умножения, просуммировать результаты (кроме нижней строки) и поделить на количество начальных отрезков, чтобы вычислить относительную стоимость в виде числа, кратного стоимости полного прохода по всем данным. Для простоты в расчет затрат мы включаем и фиктивные отрезки, что дает верхнюю границу истинной стоимости.