           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<N)────────────────────┘
                               ┌───────────────────────────────────────────┐
                        if(┐s) │ Пересылка  K[N+1]...K[2*N] в K[1]...K[N]  │
                               └───────────────────────────────────────────┘
                        Конец алгоритма

           Время работы алгоритма t примерно оценивается формулой:
                   t=a*N*lgN + b*N
        где a,b - неизвестные константы, зависящие от программной реализа-
        ции алгоритма.

           4.3. Слияние связанных списков

           В процессе  работы алгоритмов 4.1 и 4.2 половина памяти постоянно
        не используется,  а остается зарезервированной для последующего  за-
        полнения. Более логичной структурой данных является связаный список.
        В этом случае все манипуляции с  данными  заменяются  операциями  со
        связями, присутствующими  в  каждом элементе файла. Затраты памяти в
        этом случае те же,  что и при добавлении второго пространства памяти
        под  исходный файл,  однако время работы может быть меньше,  так как
        записи не перемещаются. Файл данных содержит ключи K[1]...K[N] и по-
        ля связи L[1] ... L[N], в которых могут храниться числа от -(N+1) до
        +(N+1).  В начале и в  конце  файла  имеются  искусственные элементы
        K[0],L[0] и K[N+1],L[N+1].После завершения сортировки L[0] указывает
        на наименьший ключ,  для записи к с наибольшим ключом L[k]=0.  В на-
        чале каждого шага  алгоритма  K[0]  и  K[N+1] являются головами двух
        подсписков, которые в данный момент сливаются.  Отрицательная  связь
        означает конец списка,  о котором известно, что он упорядочен. Нуле-
        вая связь означает конец последнего списка. Через │L[s]│=p обозначе-
        на операция  присваивания значения p с сохранением старого знака пе-
        ременной L[s]. Иллюстрация работы алгоритма дана  для  файла  из  16
        элементов.

         j │ 0   1  2   3  4  5   6   7   8   9  10  11  12  13  14  15  16 17
       ────┼──────────────────────────────────────────────────────────────────
       K[j]│ -  503    512   908     897    653     154     612     765     -
           │        87    61     170    275     426     509     677      703
           │
       L[j]│ 1  -3 -4  -5 -6  -7  -8 -9 -10 -11 -12 -13 -14 -15 -16   0   0  2
           │
       L[j]│ 2  -6  1  -8  3  -10  5 -11  7 -13   9  12 -16  14   0   0  15  4
           │
       L[j]│ 4   3  1 -11  2  -13  8   5  7   0   12  10  9  14  16   0  15  6
           │
       L[j]│ 4   3  6  7   2   0   8   5  1  14   12  10  13  9  16   0  15 11
           │
       L[j]│ 4  12 11  13  2   0   8   5 10  14    1   6   3  9  16   7  15  0

           Рассмотрим схему алгоритма.

          L[0]=1;L[N-1]=L[N]=0;L(N+1)=2;
                        ┌─────────────┐
         for i=1 to N-2 │ L[i]=-(i+2);│
                        └─────────────┘
      ╔> 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); ), анализируется естественное упорядочение
        участков исходного файла, и длины устанавливаются максимально воз-
        можными.
