2.3.1 The divide-and-conquer approach
merge sort
MERGE(A, p, q, r)
1 n1 ← q - p + 1
2 n2 ← r - q
3 create arrays L[1 ‥ n1 + 1] and R[1 ‥ n2 + 1]
4 for i ← 1 to n1
5 do L[i] ← A[p + i - 1]
6 for j ← 1 to n2
7 do R[j] ← A[q + j]
8 L[n1 + 1] ← ∞
9 R[n2 + 1] ← ∞
10 i ← 1
11 j ← 1
12 for k ← p to r
13 do if L[i] ≤ R[j]
14 then A[k] ← L[i]
15 i ← i + 1
16 else A[k] ← R[j]
17 j ← j + 1
MERGE-SORT(A, p, r)
1 if p < r
2 then q ← ⌊(p + r)/2⌋
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 MERGE(A, p, q, r)
代码
var n,i:integer;
a:array[1..100] of integer;
procedure mergesort(p,q,r:integer);
var n1,n2,i,j,k:integer;
al,ar:array[1..100] of integer;
begin
n1:=q-p+1;
n2:=r-q;
for i:=1 to n1 do al[i]:=a[p+i-1];
al[n1+1]:=maxint;
for i:=1 to n2 do ar[i]:=a[q+i];
ar[n2+1]:=maxint;
i:=1;j:=1;
for k:=p to r do
if al[i]<ar[j] then begin a[k]:=al[i];inc(i);end
else begin a[k]:=ar[j];inc(j);end;
end;
procedure merge(l,r:integer);
var i,q:integer;
begin
if r>l then
begin
q:=(r-l) div 2;
merge(l,l+q);
merge(l+q+1,r);
mergesort(l,l+q,r);
end;
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
merge(1,n);
for i:=1 to n do write(a[i],' ');
end.