Merge sort


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;

Pascal source (421a.sort.p)



© Addison-Wesley Publishing Co. Inc.