function sort( var r : list; n : integer ) : list;
label 999;
var fi, la, temp : list;
begin
if r = nil then sort := nil
else if n>2 then
sort := merge( sort( r, n div 2 ), sort( r, (n+1) div 2 ))
else begin
fi := r; la := r;
r := r^.next;
{*** Build list as long as possible ***}
while r <> nil do
if r^.k >= la^.k then begin
la^.next := r;
la := r;
r := r^.next;
end
else if r^.k <= fi^.k then begin
temp := r;
r := r^.next;
temp^.next := fi;
fi := temp
end
else goto 999;
999:
la^.next := nil;
sort := fi
end
end;
|