3. Сортировка многопутевым слиянием

Затраты на любую последовательную сортировку пропорциональны числу требуемых проходов, так как по определению при каждом из проходов копируются все данные. Один из способов сократить это число – распределять серии в более чем две последовательности (ленты).

Допустим, исходная последовательность хранится на ленте а. Кроме того, используются r дополнительных лент: b₁, b₂ , …, b_r. Тогда r-путевое слияние выполняется следующим образом: первая серия на ленте а распределяется на ленту b₁, вторая  на ленту b₂ и т. д., r-ая серия  на ленту b_r; затем (r+1)-ая серия на ленту b₁, (r+2)-ая  на ленту b₂ и так до тех пор, пока не распределится последняя из серий ленты а. Затем начальные серии всех дополнительных лент, сливаются на ленту а в одну общую серию, вторые серии дополнительных лент сливаются во вторую серию на ленту а и т. д. Подобный процесс может быть представлен схемой, показанной на рисунке 11.8.

Рисунок 11.8  Схема r-путевого слияния

Таким образом, естественное слияния является 2‑х путевым слиянием.

Слияние p серий поровну распределенных в r последовательностей (лент) даст в результате p/r серий. Второй проход уменьшит это число до р/r², третий – до р/r³ и т. д., после k проходов останется r/p^k серий. Поэтому общее число проходов, необходимых для сортировки N элементов с помощью r-путевого слияния, равно k=log_rN. Поскольку в каждом проходе выполняется N операций копирования, то в самом плохом случае понадобится Nlog_rN таких операций.

На практике многопутевое слияние реализуется как сбалансированное многопутевое слияние с одной единственной фазой, которое предполагает, что в каждом проходе участвует равное количество входных и выходных файлов (лент), в которые по очереди распределяются последовательные серии. Такой алгоритм использует r лент (r  четное число), поэтому он базируется на (r/2)-путевом слиянии. Фазы разделения и слияния как бы объединяются в одну фазу, в ходе которой серии из r/2 лент, называемых входными, не сливаются в одну общую последовательность, а тут же разделяются на другие r/2 лент (они называются выходными), после чего входные и выходные последовательности меняются местами.

4. Многофазная сортировка

В основе усовершенствований, реализованных в многофазной сортировке (Polyphase Sort), лежит отказ от жесткого понятия прохода и переход к более изощренному использованию последовательностей, называемых лентами. Этот метод был изобретен Р. Гилстэдом.

Продемонстрируем многофазную сортировку на примере с тремя последовательностями (лентами) f1, f2 и f3. В каждый момент сливаются элементы из двух лент-источников и записываются в третью ленту. Как только одна из входных последовательностей исчерпывается, она сразу же становится выходной для операции слияния из оставшейся, неисчерпанной входной последовательности и предыдущей выходной.

Поскольку известно, что p серий на каждом из входов трансформируются в p серий на выходе, то нужно только держать список из числа серий в каждой последовательности (а не определять их действительные ключи). Будем считать, что в начале две входные последовательности f1 и f2 содержат соответственно 13 и 8 серий. Следовательно, на первом проходе 8 серий из f1 и f2 сливаются в f3, на втором – 5 серий из f1 и f3 и сливаются в f2 и т. д. В конце концов, в f1 оказывается отсортированная последовательность. Этот процесс показан на рисунке 11.9.

Рисунок 11.9  Многофазная сортировка слиянием 21 серии на трех лентах

Многофазная сортировка более эффективна, чем сбалансированная многопутевая, поскольку она имеет дело с (r-1)-путевым слиянием, а не с (r/2)-путевым слиянием, если она начинается с r последовательностей (лент). Ведь число необходимых проходов приблизительно равно log_rN , где N – число сортируемых элементов, а r – степень операции слияния, – это и определяет значительное преимущество многофазной сортировки.