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

Рис. 5 иллюстрирует сортировку слиянием, когда мы продвигаемся с обоих концов, подобно методам быстрой сортировки, обменной сортировки и т.д. Мы анализируем исходный файл слева и справа, двигаясь к середине. Пропустим первую строку и рассмотрим вторую. Слева мы видим возрастающий отрезок 503 703 765, а справа, если читать справа налево, имеем отрезок 087 512 677. Слияние этих двух последовательностей дает подфайл 087 503 512 677 703 765, который перемещается слева в строке 3. Затем ключи 061 612 908 в строке 2 сливаются с 170 509 987 и результат записывается справа в строке 3. Наконец, 154 275 426 653 сливается с 653 (перекрытие обнаруживается раньше, чем оно может привести к нежелательным последствиям) и результат записывается слева. Точно также строка 2 получилась из исходного файла в строке 1.

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

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

Алгоритм Е (Сортировка естественным двухпутевым слиянием).

При сортировке записей R₁, …, R_N используются две области памяти, каждая из которых может содержать N записей. Для удобства обозначим записи, находящиеся во второй области, через R_N+1, …, R_2N, хотя в действительности области не обязательно идти друг за другом. Начальное содержание второй области не имеет значение. После завершения алгоритма ключи будут упорядочены К₁ £ …£ К_N.

Блок-схема, построенная в соответствии с принципами структурного программирования

(Начальная установка) Установить s:=0 (при s=0 мы будем пересылать записи из области (R₁,…R_N) в область (R_N+1, …, R_2N); при s=1 наоборот.)

(Подготовиться к просмотру) Если s=0, то установить i:=1, j:=N, k:=N+1, g:=2N, если s=1, то установить i:=N+1, j:=2N, k:=1, g:=N. (переменные i, j, k, g указывают текущие позиции во входных "файлах", откуда идет чтение, и в "выходных" файлах, куда идет запись; i и k – левые позиции, j и r – правые позиции.) Установить d:=1, f:=1 (Переменные d определяет текущее направление вывода, f устанавливается равной 0, если необходимы дальнейшие просмотры.)

(Сравнения К_i с К_j) Если К_i > К_j, то перейти к шагу Е8, если i=j (т.е. рассматриваем один и тот же элемент с разных концов), то установить R_k:=R_i и перейти к шагу Е13.

(Пересылка R_i) (Шаги Е4-Е7 аналогичны шагам М3-М4 алгоритма М). Установить R_k:=R_i, k:=k+d.

(Ступенька вниз?) Увеличить i на 1, Затем, если К_i–1 £ К_i, то возвратиться к шагу Е3.

(Пересылка R_j) Установить R_k:=R_j, k:=k+d.

(Ступенька вниз?). Уменьшить j на 1. Затем, если К_j+1 £ К_j, то возвратиться к шагу Е6, в противном случае перейти к шагу Е12.

(Пересылка R_j) (Шаги Е8–Е11 двойственные по отношению к шагам Е4–Е7) Установить R_k:=R_j, k:=k+d.

(Ступенька вниз?). Уменьшить j на 1. Затем, если К_j+1 £ К_j, то возвратиться к шагу Е3

(Пересылка R_j) Установить R_k:=R_i, k:=k+d.

(Ступенька вниз?). Увеличить i на 1, Затем, если К_i–1 £ К_i, то возвратиться к шагу Е10.

(Переключение направления). Установить f:=0, d:= – d и взаимозаменить k <-> g. Возвратиться к шагу Е3.

(Переключение областей) Если f=0, то установить s:=1–s и возвратиться к шагу Е2, в противном случае сортировка завершена, если s=0, то установить (R₁,…R_N):= (R_N+1, …, R_2N) (если это критично).

Если исходный файл случаен, то в нем около 1/2N возрастающих отрезков, так как К_i > К_i+1 с вероятностью 1/2. При каждом просмотре число отрезков сокращается вдвое. Число просмотров, как правило, составляет около lоg₂ N. При каждом просмотре мы должны переписать все N записей, и большая часть времени затрачивается в шагах Е3, Е4, Е5, Е8, Е9. Общее время работы асимптотически приближается к 12.5Nlоg₂N, как в среднем, так и худшем варианте. Это медленнее быстрой сортировки и не настолько лучше пирамидальной сортировки (16lоg₂N), чтобы оправдать вдвое больший расход памяти.