4. Сортировка посредством слияния Алгоритмы сортировки этого класса основываются на объединении нескольких (часто двух) уже упорядоченнх файлов. Рассмотренные далее алгоритмы выбирают из исходного файла упорядоченные отрезки и объ- единяют их в более длинные. 4.1. Естественное двухпутевое слияние Этот алгоритм ищет упорядоченные отрезки с двух концов файла и переписывает их по очереди также в оба конца. Повторяя эту процедуру в цикле, мы приходим к середине файла, что означает окончание сорти- ровки. Проиллюстрируем работу алгоритма на примере файла из 16 эле- ментов: ┌─<───────────────────────────────────────────────────<─1─┐ │ ┌─2─>──────────────────────────────────────>─┐ │ │ │ ┌─<────────────────────────────<─3┐ │ │ │ │ │ ┌4─>─────────────────>┐ │ │ │ │ │ │ │ ┌<────<5┐ │ │ │ │ 503│87 512│61 908│170 897│275 653│426 154│509│612│677│765 703 -> -> -> -> -> <- <- <- <- <- Черточками разделены упорядоченные отрезки, стрелками показаны направления урорядочения внутри отрезков. На первом шаге сливаются отрезки 503 слева и 703 765 справа в один отрезок, который записыва- ется в левый конец файла, на втором шаге сливаются отрезки 87 512 слева и 677 справа, которые записываются в правый конец файла и т.д. Это показано на рисунке линиями со стрелками и номерами действий. В результате файл принимает следующий вид: 503 703 765│ 61 612 908│ 154 275 426 │653│ 897 509 170 │677 512 87 -> -> -> -> <- <- <- Дальнейшие шаги дают следующие результаты: 87 503 512 703 765 │154 275 426 │653 │ 908 897 612 509 170 61 -> -> -> <- <- 61 87 170 503 509 512 612 677 703 765 897 │ 908 │ 653 426 275 154 -> -> <- <- 61 87 154 170 275 426 503 509 512 612 653 677 703 765 897 │ 908 │ -> <- Рассмотрим алгоритм. Для хранения второго "экземпляра" файла об- разована новая область, располагающаяся вслед за исходной областью K[1], K[2], ... K[N] c индексами от N+1 до 2*N: K[N+1] ... K[2*N]. Элементы файла пересылаются из одной области в другую, меняя направ- ление пересылки. Для запоминания направления пересылки служит пере- менная s, принимающая значения TRUE и FALSE попеременно. Другой ло- гический признак f служит сигналом продолжения-окончания алгоритма, если все области слились в конце концов в одну. Переменная d прини- мает попеременно значения +1 -1 и указывает направление просмотра файла: вперед или назад.Операция <-> обозначает обмен значениями двух переменных. Операция ┐ обозначает инверсию логической перемен- ной или выражения. s=true; ┌───────────────────────────────────────────────do────────────────────┐ │ then if(s) else │ │ ╔═════════<═══╩═══>═══════════════╗ │ │┌──╨─────────────────┐ ┌─────────────╨──────┐ │ ││i=1;j=N;k=N+1;l=2*N;│ │k=1;l=N;i=N+1;j=2*N;│ │ │└──╥─────────────────┘ └─────────────╥──────┘ │ │ ╚═════════>═══════╦════<══════════╝ │ │ d=1; f=false; │ │ ╔════════════════>╩<═════════════════════════════════════════╗ │ │ ║ then if(K[i]<=K[j]) else ║ │ │ ║ ╔═════════<═══╩═══>═════════════╗ ║ │ │ ║┌──╨──────────────────────┐ ║ ┌────────────────┐ ║ │ │ ║│ if(i=j) ══>════>═════>═╪═══>════╬══>══│K[k]=K[i]; s=┐s;╞═╬═══>╡ │ ║│ │ ║ └────────────────┘ ║ │ │ ║│ K[k]=K[i]; │ ┌──╨──────────────────────┐ ║ │ │ ║│ k=k+d; │ │ K[k]=K[j]; │ ║ │ │ ║│ i=i+1; │ │ k=k+d; │ ║ │ │ ║│ if(K[i-1] <= K[i])═>╗ │ │ j=j-1; │ ║ │ │ ╠╪═════════════<═══════╝ │ │ if(K[j+1] <= K[j])═>════╪═╝ │ │ ║│ ┌─────────────do─────┐ │ │ ┌─────────────do─────┐ │ │ │ ║│ │ K[k]=K[j]; │ │ │ │ K[k]=K[i]; │ │ │ │ ║│ │ k=k+d; │ │ │ │ k=k+d; │ │ │ │ ║│ │ j=j-1; │ │ │ │ i=i+1; │ │ │ │ ║│ └─while(K[j+1]<=K[j])┘ │ │ └─while(K[i-1]<=K[i])┘ │ │ │ ║└───────────╥─────────────┘ └─────────────────────╥───┘ │ │ ║ ╚═══════>╦<════════════════<══════════════╝ │ │ ║ ┌────╨───────────────────┐ │ │ ║ │ f=true; d=-d; k <-> l; │ │ │ ║ └────╥───────────────────┘ │ │ ╚═════════════════════╝ │ └───────────────────────────────while(f) ─────────────────────────────┘ ┌──────────────────────────────────────────────┐ if(┐s)│ Пересылка K[N+1]...K[2*N] в K[1]...K[N] │ └──────────────────────────────────────────────┘ Конец алгоритма; Время работы алгоритма t примерно оценивается формулой: t=a*N*lgN + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 4.2. Простое двухпутевое слияние. В алгоритме естественного двухпутевого слияния упорядоченный от- резки файла определялись случайным расположением элементов в исход- ном файле. В данном алгоритме длина отрезков фиксируется на каждом шаге. В исходной файле все отрезки имеют длину 1, после первого шага она равна 2, после второго 4, после третьего - 8, после к-го шага - 2 в степени к. Иллюстрация работы алгоритма приведена ниже. Исходный файл имеет вид: 503│ 87│512│61 │908│170│897│275│653│426│154│509│612│677│765│703 Черточками разделены отрезки. Стрелками обозначено направление упорядочения. В дальнейшем файл преобразуется следующим образом. 503 703│512 677│509 908│426 897│653 275│170 154│612 61│765 87 -> -> -> -> <- <- <- <- 87 503 703 765│154 170 509 908│897 653 426 275│677 612 512 61 -> -> <- <- 61 87 503 512 612 677 703 765│908 897 653 509 426 275 170 154 -> <- 61 87 154 170 275 426 503 509 512 612 653 677 703 765 897 908 -> Рассмотрим алгоритм. Для хранения второго "экземпляра" файла об- разована новая область, располагающаяся вслед за исходной областью K[1], K[2], ... K[N] c индексами от N+1 до 2*N: K[N+1] ... K[2*N]. Элементы файла пересылаются из одной области в другую, меняя направ- ление пересылки. Для запоминания направления пересылки служит пере- менная s, принимающая значения TRUE и FALSE попеременно. Переменная p имеет значение размера отрезков, которые будут сливаться на предс- тоящем шаге, q и r - количества неслитых еще элементов в отрезках. Переменная d принимает попеременно значения +1 -1 и указывает нап- равление просмотра файла: вперед или назад.Операция  обозначает об- мен значениями двух переменных. Операция ┐ обозначает инверсию логи- ческой переменной или выражения. Алгоритм имеет следующий вид. s=true;p=1; ┌─────────────────────────────────────────────────do───────────────────┐ │ then if(s) else │ │ ╔═════════<═══╩═══>═══════════════╗ │ │ ┌──╨─────────────────┐ ┌─────────────╨──────┐ │ │ │i=1;j=N;k=N+1;l=2*N;│ │k=1;l=N;i=N+1;j=2*N;│ │ │ └──╥─────────────────┘ └─────────────╥──────┘ │ │ ╚═════════>═══════╦════<══════════╝ │ │ d=1; q=p; r=p; │ │ ╔══════════════>══╬══<═══════════════════════════════════════╗ │ │ ║ if(K[i] <= K[j]) ║ │ │ ║ then ║ else ║ │ │ ║ ╔═════════<═══╩═══>═════════════╗ ║ │ │ ║┌──╨──────────────────────┐ ┌──╨────────────────┐ ║ │ │ ║│ k=k+d; │ │ k=k+d; │ ║ │ │ ║│ K[k]=K[i]; │ │ K[k]=K[j]; │ ║ │ │ ║│ i=i+1; │ │ j=j-1; │ ║ │ │ ║│ q=q-1; │ │ r=r-1; │ ║ │ │ ║│ if(q>0)════════════>╗ │ │ if(r>0)═══════════╪═══════╝ │ │ ╠╪═════════════<═══════╝ │ │ ┌──────────do──┐ │ │ │ ║│ ┌─────────do───┐ │ │ │ k=k+d; │ │ │ │ ║│ │ k=k+d; │ │ │ │ if(k=l)═>══╗ │ │ ┌──────┐ │ │ ║│ │ if(k=l) ══>══╪═══════╪══>══╪══╪═════════>══╩═╪═╪══╡p=p+p;╞═>╡ │ ║│ │ K[k]=K[j] │ │ │ │ K[k]=K[i] │ │ │s=┐s; │ │ │ ║│ │ j=j-1;r=r-1; │ │ │ │ i=i+1; q=q-1;│ │ └──────┘ │ │ ║│ └while(r>0)────┘ │ │ └while(q>0)────┘ │ │ │ ║└───────────╥─────────────┘ └───────────╥───────┘ │ │ ║ ╚═══════>╦<════════════════<════╝ │ │ ║ ┌────╨───────────────────┐ │ │ ║ │ q=p;r=p;d=-d; k <-> l; │ │ │ ║ └────╥───────────────────┘ │ │ ╚═══════<═════════════╝ │ └────────────────────────────────────────while(p s=0; t=N+1; ║ p=L[s]; q=L[t]; ║ if(q=0) Конец алгоритма; ║ ╔═════>══════════════════╦═════════<══════════════════╦══<═╗ ║ ║ if(K[p]<=K[q]) ║ ║ ║ ║ then ║ else ║ ║ ║ ║ ╔═══════════════<═══╩════>════════════╗ ║ ║ ║ ║ │L[s]│=p; │L[s]│=q; ║ ║ ║ ║ s=p; p=L[p]; s=q; q=L[q]; ║ ║ ║ ║ if(p>0) ═>╗ if(q>0) ═>═════╝ ║ ║ ╚════<══════╝ ║ ║ │L[s]│=q; L[s] =p; ║ ║ s=t; s=t; ║ ║ ╔═══<═════════╗ ╔═══<═════════╗ ║ ║ t=q; q=L[q]; ║ t=p; p=L[p]; ║ ║ ║ if (q>0) ═>════╝ if (p>0) ═>════╝ ║ ║ else ═════>═════════════════════╗ else ═>═╗ ║ ║ ╠══<══════════╝ ║ ║ p=-p; ║ ║ q=-q; ║ ║ if(q=0) ║ ║ then ║ else ║ ║ ╔════════════════════<════╩════>══════════════════╝ ║ │L[s]│=p; │L[t]│=0; ╚══════<════╝ Время работы алгоритма t примерно оценивается формулой: t=a*N*lgN + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. Этот метод допускает естественную модификацию, заключающуюся в том, что вместо начальной установки длин всех списков, равных 1 ( оператор L[i]=-(i+2); ), анализируется естественное упорядочение участков исходного файла, и длины устанавливаются максимально воз- можными.