Сортировка слияниями

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

Пусть имеется массив чисел. Делим его рекурсивно на подмассивы, содержащие по одному элементу – такие массивы считаем упорядоченными. Далее происходит слияние одноэлементных массивов в упорядоченные пары. Упорядоченные пары затем сливаются в упорядоченные четвёрки и так далее.

Как видим, наибольшую трудность представляет написание процедуры слияния. В остальном алгоритм не особо сложен.

Сначала я попытаюсь сделать наброски задуманного на старом добром Турбо Паскале 7.0. Раз уж я замахнулся на сортировку слияниями применительно к массивам, то в первую очередь хочу заметить, что в таком случае мне понадобится больше памяти, чем хотелось бы, а именно в 2 раза больше – под 2 таких массива. Связано это с тем, что в процессе слияния исходный массив каждый раз переписывается, а для этого необходим буфер.

Const
  nmax = 2000; {максимальное число элементов}
Var
  a, p: array[0..nmax-1] of integer; {сортируемый и буферный массивы}
Procedure Merge(L, M, R: integer); {процедура слияния}
  Var
    i, j, k: integer;
  Begin
    i:=L;
    j:=M;
    k:=L;
    For k:=L To R Do {проходим по элементам от L-го до R-го}
      If (j > R) Or (i < M) And (a[i] < a[j]) Then Begin
        p[k]:=a[i]; {в p[k] кладётся меньший элемент}
        inc(i) End
      Else Begin
        p[k]:=a[j]; {и здесь тоже}
        inc(j);
      End;
    For k:=L To R Do
      a[k]:=p[k]; {p использовался как буфер; переносим его содержимое в a}
  End;

Procedure Sort(L, R: integer);
  Var
    M: integer;
  Begin
    M:=(L+R+1) Shr 1;
    If L < M Then
      Sort(L, M-1);
    If M < R Then
      Sort(M, R);
    Merge(L, M, R);
  End;

Предлагаю ознакомиться с разбором реализации алгоритма на ассемблере. Мне кажется, ассемблерные коды – это очень красиво! Тем более, ассемблерные реализации суть главная цель данной статьи.