F. 归并排序{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
for i:=2 to n do begin
a[0]:=a[i];
j:=i-1;
while a[0]<a[j] do begin
a[j+1]:=a[j];
j:=j-1;
end;
a[j+1]:=a[0];
end;
end;{inset_sort}

begin
for i:=1 to n-1 do
for j:=n downto i+1 do
if a[j]<a[j-1] then swap( a[j],a[j-1]); {每次比较相邻元素的关系}
end;

begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then len:=a[0] else len:=b[0];
for i:=1 to len do begin
inc(c[i],a[i]+b[i]);
if c[i]>10 then begin dec(c[i],10); inc(c[i+1]); end; {进位}
end;
if c[len+1]>0 then inc(len);
c[0]:=len;
end;{plus}

begin
fillchar(c,sizeof(c),0);
len:=a[0];
for i:=1 to len do begin
inc(c[i],a[i]*b);
inc(c[i+1],(a[i]*b) div 10);
c[i]:=c[i] mod 10;
end;
inc(len);
while (c[len]>=10) do begin {处理最高位的进位}
c[len+1]:=c[len] div 10;
c[len]:=c[len] mod 10;
inc(len);
end;
while (len>1) and (c[len]=0) do dec(len); {若不需进位则调整len}
c[0]:=len;
end;{multiply}

begin
fillchar(c,sizeof(c),0);
len:=a[0]; d:=0;
for i:=len downto 1 do begin
d:=d*10+a[i];
c[i]:=d div b;
d:=d mod b;
end;
while (len>1) and (c[len]=0) then dec(len);
c[0]:=len;
end;

begin
p:=L.head; j:=0;
if (I>=1) and (I<=L.len) then
while j<I do begin p:=p^.next; inc(j); end;
loc:=p;
end;

begin
p:=loc(L,I-1);
q:=p^.next;
p^.next:=q^.next;
dispose(q);
dec(L.len);
end;

【问题1】（8分）
（1）k<=r
（2）arr[k]=right[j]
（3）begin<end
（4）mergeSort(arr,mid+1,end)

【问题2】（5分）
（5）分治
（6）T(n)=2T(n/2)+O(n)
（7）O(nlogn)
（8）O(n)

【问题3】（2分）
（9）n1+n2

begin
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then swap(a[i],a[j]);
end;

begin
a[0]:=a[i]; k:=2*i;{在完全二叉树中结点i的左孩子为2*i,右孩子为2*i+1}
while k<=m do begin
if (k<m) and (a[k]<a[k+1]) then inc(k);{找出a[k]与a[k+1]中较大值}
if a[0]<a[k] then begin a[i]:=a[k];i:=k;k:=2*i; end
else k:=m+1;
end;
a[i]:=a[0]; {将根放在合适的位置}
end;

procedure heapsort;
var
j:integer;
begin
for j:=n div 2 downto 1 do sift(j,n);
for j:=n downto 2 do begin
swap(a[1],a[j]);
sift(1,j-1);
end;
end;

begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then len:=a[0] else len:=b[0];
for i:=1 to len do begin
inc(c[i],a[i]-b[i]);
if c[i]<0 then begin inc(c[i],10);dec(c[i+1]); end;
while (len>1) and (c[len]=0) do dec(len);
c[0]:=len;
end;

begin
fillchar(c,sizeof(c),0);
for i:=1 to a[0] do
for j:=1 to b[0] do begin
inc(c[i+j-1],a[i]*b[j]);
inc(c[i+j],c[i+j-1] div 10);
c[i+j-1]:=c[i+j-1] mod 10;
end;
len:=a[0]+b[0]+1;
while (len>1) and (c[len]=0) do dec(len);
c[0]:=len;
end;

begin
if (pre='''') or (mid='''') then exit;
i:=pos(pre[1],mid);
solve(copy(pre,2,i),copy(mid,1,i-1));
solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i));
post:=post+pre[1]; {加上根，递归结束后post即为后序遍历}
end;

begin
p:=loc(L,I);
new(q);
q^.data:=x;
q^.next:=p^.next;
p^.next:=q;
inc(L.len);
end;