归并排序算法

[其他]代码库

{a为序列表，tmp为辅助数组}
procedure merge(var a:listtype; p,q,r:integer);
{将已排序好的子序列a[p..q]与a[q+1..r]合并为有序的tmp[p..r]}
var I,j,t:integer;
   tmp:listtype;
begin
  t:=p;i:=p;j:=q+1;{t为tmp指针，I,j分别为左右子序列的指针}
  while (t<=r) do begin
    if (i<=q){左序列有剩余} and ((j>r) or (a[i]<=a[j])) {满足取左边序列当前元素的要求}
      then begin
            tmp[t]:=a[i]; inc(i);
      end
    else begin
          tmp[t]:=a[j];inc(j);
    end;
  inc(t);
end;
for i:=p to r do a[i]:=tmp[i];
end;{merge}

procedure merge_sort(var a:listtype; p,r: integer); {合并排序a[p..r]}
var  q:integer;
begin
  if p<>r then begin
    q:=(p+r-1) div 2;
    merge_sort (a,p,q);
    merge_sort (a,q+1,r);
    merge (a,p,q,r);
  end;
end;
{main}
begin
merge_sort(a,1,n);
end.