2. Сортировка естественным слиянием

В случае простого слияния мы ничего не выигрываем, если данные уже частично рассортированы. На k-м проходе длина всех сливаемых последовательностей меньше или равна 2^k. При этом не учитывается то, что более длинные последовательности могут быть уже упорядочены и, следовательно, их можно сливать. Фактически можно было бы сразу сливать какие-либо упорядоченные подпоследовательности длиной m и k в одну последовательность из m+k элементов. Метод сортировки, при котором каждый раз сливаются две самые длинные возможные подпоследовательности, называется естественным слиянием.

Упорядоченную подпоследовательность часто называют цепочкой. Но, поскольку слово «цепочка» чаще используется для обозначения односвязного списка, мы будем использовать слово серия, когда речь идет об упорядоченной подпоследовательности. Сортировка естественным слиянием сливает последовательности не фиксированной длины, а серии. Серии имеют то свойство, что при слиянии двух последовательностей, каждая из которых содержит n серий, возникает одна последовательность, содержащая ровно n/2 серий. Таким образом, на каждом проходе общее число серий уменьшается вдвое, и число необходимых пересылок элементов в худшем случае равно Nlog₂N, а в обычном случае даже меньше. Ожидаемое число сравнений, однако, намного больше, так как кроме сравнений, необходимых для упорядочения элементов, требуются еще сравнения соседних элементов каждого файла для определения концов серии.

Пусть исходная последовательность элементов задана в виде файла а, который в конце работы должен содержать результат сортировки. Используются две вспомогательные ленты b и с. Каждый проход состоит из фазы распределения, которая распределяет серии поровну из а в b и с, и фазы слияния, которая сливает серии из b и с в а. В качестве примера ниже показан файл а в исходном состоянии (строка 1) и после каждого прохода (строки 2  4). В естественном слиянии участвуют 20 чисел. Заметим, что требуются только три прохода. Сортировка заканчивается, как только число серий в а будет равно 1. (Предполагается, что в исходном файле имеется хотя бы одна непустая серия.)

17, 31, | 05, 59, | 13, 41, 43, 67, | 11, 23, 29, 47, | 03, 07, 71, | 02, 19, 57, | 37, 61

05, 17, 31, 59, | 11, 13, 23, 29, 41, 43, 47, 67, | 02, 03, 07, 19, 57, 71, | 37, 61

05, 11, 13, 17, 23, 29, 31, 41, 43, 47, 59, 67, | 02, 03, 07, 19, 37, 57, 61, 71

02, 03, 05, 07, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 57, 59, 61, 67, 71

Схематично процесс сортировки естественным слиянием можно отобразить рисунком 11.7.

Рисунок 11.7  Фазы сортировки естественным слиянием

При просмотре последовательности, выполняемом на фазе разделения (распределения) определяется конец очередной серии. Элемент, расположенный на конце предыдущей серии должен быть больше первого элемента следующей серии, т. е. нужно сравнивать ключи двух последовательных элементов. Однако природа последовательности такова, что непосредственно доступен только один-единственный элемент. Поэтому невозможно избежать «заглядывания вперед», т. е. необходимо считывать в некий «буфер» первый еще не считанный элемент последовательности.

Процесс сравнения и выбора ключей при слиянии заканчивается, как только исчерпана одна из двух серий. После этого оставшаяся неисчерпанной серия должна быть просто передана в результирующую серию, т.е. скопирована в ее «хвост».