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

Рис. 11.16. Распределение отрезков для полифазного трехпутевого слияния
При начальном распределении для полифазного трехпутевого слияния файла, размер которого в 17 раз больше объема оперативной памяти, мы помещаем 7 отрезков на устройство 0, 4 отрезка на устройство 2 и 6 отрезков на устройство 3. Затем на первой фазе мы выполняем слияния до исчерпания устройства 2, при этом на устройстве 0 остаются 3 отрезка размером 1, на устройстве 3 - 2 отрезка размером 1, и на устройстве 1 - вновь созданные 4 отрезка размером 3. Для файла, в 15 раз большего объема оперативной памяти, мы вначале помещаем на устройство 0 два фиктивных отрезка (см. рис. 11.15). Общее количество обработанных в процессе полного слияния отрезков равно 59, т.е. на один меньше, чем в примере сбалансированного слияния (см. рис. 11.13), но при этом используется на 2устройства меньше (см. также упражнение 11.50).
Лемма 11.6. При наличии трех внешних устройств и оперативной памяти, достаточной для размещения M записей, сортировка-слияние, основанная на выборке с замещением с последующим двухпутевым полифазным слиянием, выполняет в среднем порядка   эффективных проходов.
Общий анализ полифазного слияния, выполненный Кнутом (Knuth) и другими исследователями в шестидесятых-семидесятых годах - сложное и пространное исследование, выходящее за рамки данной книги. Для P = 3 используются числа Фибоначчи, отсюда и появление коэффициента ф. Для больших P появляются другие константы. Коэффициент 1/ф отражает тот факт, что на каждой фазе используется лишь часть данных. Мы считаем количеством " эффективных проходов " количество прочитанных данных, деленное на общее количество данных. Некоторые результаты общего анализа вызывают удивление. К примеру, оптимальный метод распределения фиктивных отрезков по устройствам использует дополнительные фазы и большее количество фиктивных отрезков, чем можно бы было предположить, поскольку некоторые отрезки используются в слияниях намного чаще других (см. раздел ссылок). 
Например, если нужно отсортировать 1 миллиард записей, используя 3 устройства и оперативную память, достаточную для размещения 1 миллиона записей, то с помощью двухпутевого полифазного слияния это можно сделать за   проходов. Добавив проход начального распределения, мы получаем несколько большие затраты (один проход), чем для сбалансированного слияния, использующего вдвое больше устройств. То есть можно считать, что полифазное слияние позволяет выполнить ту же работу, но с половиной внешних устройств. Для заданного количества устройств поли-фазное слияние всегда более эффективно, чем сбалансированное слияние, о чем свидетельствует рис. 11.17.
Как было сказано в начале раздела 11.3, сосредоточение нашего внимания на абстрактной машине с последовательным доступом к внешним устройствам позволило отделить вопросы, связанные с разработкой алгоритмов, от практических вопросов. При разработке практических приложений необходимо проверять, соблюдаются ли наши основные предположения. Например, мы зависим от эффективной реализации функций ввода-вывода, которые передают данные между процессором и внешними устройствами, и других системных программных средств. В современных системах такие программные средства обычно хорошо отлажены.