PROGRAM quicksort; (* * from CACM October 1978, page 847 * "Implementing Quicksort Programs" by R. Sedgewick *) CONST N=15000; stksize=60; insertparam=20; TYPE index=0..N; VAR A: ARRAY[index] OF integer; l,r,i,j,m:index; v,t: integer; s: 0..stksize; stack:ARRAY[1..stksize] OF RECORD l,r: index END; BEGIN FOR i:=1 to N do A[i]:=i mod 500; A[0]:= -maxint; s:=1; stack[1].l:=1; stack[1].r:=N; REPEAT (* Unstack and partition next sublist *) l:=stack[s].l; r:=stack[s].r; s:=s-1; WHILE r-l>insertparam DO BEGIN m:=(l+r) DIV 2; t:=A[m]; A[m]:=A[l+1]; A[l+1]:=t; IF A[l+1]>A[r] THEN BEGIN t:=A[l+1]; A[l+1]:=A[r]; A[r]:=t END; IF A[l]>A[r] THEN BEGIN t:=A[l]; A[l]:=A[r]; A[r]:=t END; IF A[l+1]>A[l] THEN BEGIN t:=A[l+1]; A[l+1]:=A[l]; A[l]:=t END; i:=l+1; j:=r; v:=A[l]; REPEAT REPEAT i:=i+1 UNTIL A[i]>=v; REPEAT j:=j-1 UNTIL A[j]<=v; IF ij; A[l]:=A[j]; A[j]:=v; s:=s+1; IF i-lA[l+1] THEN BEGIN v:=A[l+1]; i:=l; REPEAT A[i+1]:=A[i]; i:=i-1 UNTIL A[i]<=v; A[i+1]:=v; END; END.