function sort ( r : list ) : list;
var lowf,lowl, midf,midl, highf,highl : list;

begin
if r = nil then begin Last := nil; sort := r end
else begin
lowf := nil; midf := nil; highf := nil;
{*** First key becomes splitter ***}
tailins( r, midf, midl );
r := r^.next;
while r<>nil do begin
if r^.k else if r^.k=midf^.k then tailins(r,midf,midl)
else tailins(r,highf,highl);
r := r^.next
end;
{*** Assemble resulting list ***}
if lowf <> nil then begin
lowl^.next := nil;
sort := sort(lowf);
Last^.next := midf
end
else sort := midf;
if highf <> nil then highl^.next := nil;
midl^.next := sort(highf);
if Last = nil then Last := midl
end
end;