Quicksort for lists


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<midf^.k then tailins(r,lowf,lowl) 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;

Pascal source (422.sort.p)



© Addison-Wesley Publishing Co. Inc.