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

sort.pas

procedure StraightMergeSort;
var
  i,j,k,L,t,h,m,p,q,r:
    integer;
  bUp:
    boolean;
begin
  nMove:=0;
  nCompare:=0;

  bUp:=true;
  p:=1;


  repeat
    h:=1;
    m:=nCurr;


    if bUp then
      begin i:=1; j:=nCurr; k:=nCurr+1; L:=2*nCurr; end
    else
      begin k:=1; L:=nCurr; i:=nCurr+1; j:=2*nCurr; end;

    repeat
      if m>=p then q:=p else q:=m;
      m:=m-q;

      if m>=p then r:=p else r:=m;
      m:=m-r;


      while (q<>0) and (r<>0) do
      begin
        nCompare:=nCompare+1;

        if A[i]<A[j] then
        begin
          A[k]:=A[i];
          i:=i+1; q:=q-1;
        end
        else
        begin
          A[k]:=A[j];
          j:=j-1; r:=r-1;
        end;

        nMove:=nMove+2;
        k:=k+h;
      end;

      while r>0 do
      begin
        A[k]:=A[j];
        nMove:=nMove+2;
        k:=k+h; j:=j-1; r:=r-1;
      end;

      while q>0 do
      begin
        A[k]:=A[i];
        nMove:=nMove+2;
        k:=k+h; i:=i+1; q:=q-1;
      end;

      h:=-h; t:=k; k:=L; L:=t;

    until m=0;

    bUp:=not bUp;
    p:=2*p;

  until p>=nCurr;

  if not bUp then
    for i:=1 to nCurr do
    begin
      A[i]:=A[i+nCurr];
//      nMove:=nMove+2;
    end;
end;

Назначение глобальных переменных следующее:

A - массив single'ов размера 2*nCurr, nCurr первых из которых значащие и требуют сортировки
(вторая половина массива играет роль дополнительного массива для хранения результата сливания)

nMove - считает число пересылок данных для анализа сложности алгоритма.
nCompare - считает число сравнений с той же целью.

Назначение локальных переменных:
bUp - определяет, в какой половине A в данных момент хранятся актуальные данные, а какую можно использовать как дополнительную.
Назначение остальных переменных мне не ясно.