6.3 Естественное слияние
 

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

Представим, что исходный файл разделен на два файла, каждый из которых содержит по n серий (один может содержать (n -1) серий). Тогда при слиянии образуется файл, содержащий также n серий. При каждом проходе число серий уменьша-тся вдвое и общее число пересылок в худшем случае равно nlog₂n, а в среднем меньше.

Процесс сортировки заканчивается, если при очередном слиянии в выходной файл будет записана только одна единственная серия. Рассмотрим процесс естественного слияния на примере. Пусть исходный файл А содержит записи с ключами:
17 31 « 05 59 « 13 41 43 67 «11 23 29 47 « 03 07 71 « 02 19 57 « 37 61.

Как видим, они образуют 7 серий, которые для наглядности разделены знаками «. Разобьем файл А на два файла В и С: первую серию запишем в файл В, вторую в файл С, третью в файл В, четвертую в файл С и т.д., которые затем сольем в файл А:
Первый проход:
В: 17 31 « 13 41 43 67 « 03 07 71 « 37 61
С: 05 59 « 11 23 29 47 «02 19 57
А: 05 17 31 59 « 11 13 23 29 41 43 47 67 « 02 03 07 19 57 71 «37 61
Второй проход:
В: 05 17 31 59 «02 03 07 19 57 71
С: 11 13 23 29 41 43 47 67 « 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

Алгоритм естественного слияния выглядит так:

1. Открыть файл А как входной (для чтения).
2. Открыть файлы В и С как выходные (для записи).
3. Считывать записи и посылать их в файл В до тех пор, пока очередная запись больше предыдущей (r_i > r_i-1 ), то есть до конца серии.
4. Запись r_i ≤ r_i-1 записать в файл С. Считывать записи и посылать их в С до тех пор, пока r_i > r_i-1, то есть до конца следующей серии.
5. Выполнять пункты 3 и 4, пока не будет достигнут конец файла А.
6. Выполнить фазу слияния файлов В и С в файл А.
7. Пункты 1—5 повторять до тех пор, пока в результате слияния в выходной файл не будет записана только одна-единственная серия.

В процессе сортировки может возникнуть такая ситуация, несколько серий из файла А при разделении образуют в выходном файле В или С одну серию, в таком случае число проходов уменьшается.

Пусть в файле А находятся 6 серий:
1 ... 29 « 21 ...47 « 31 ... 55 » 49 ... 81 « 75 ... 80 « 3 ... 18.
При разделении в файлы В и С попадут серии в следующем порядке:
В: 1 ... 29 «31 ... 55 «75 ... 80
С: 21 ... 47 « 49 ... 81 « 3 ...18

В файле В три серии образовали одну серию, а в файле С первые две серии также объединились в одну. При очёредном слиянии образуется всего две серии: 1 ...81 « 3 ...18, которые сольются в одну при очередном проходе.

Если использовать четыре файла, то фазы слияния и разделения можно объединить в одну фазу. Для этого достаточно полученные при слиянии файлов В и С серии поочередно направлять в файлы D и Е, и, наоборот, если сливаются серии из файлов D и Е, полученные серии поочередно направлять в В и С.

Сортировка заканчивается, если при очередной фазе слияния - разделения образуется только одна серия и один из выходных файлов останется пустым, т.е. туда не будет записана ни одна серия.