%!

/qsortdict 8 dict def

qsortdict begin

% args: /comp a L R x
% effect: effects a partition into two pieces [L j] [i R]
%     leaves i j on stack

/partition { 8 dict begin
/x exch def
/j exch def
/i exch def
/a exch def
{
  {
    a i get x lt not {
      exit
    } if
    /i i 1 add def
  } loop
  {
    x a j get lt not {
      exit
    } if
    /j j 1 sub def
  } loop
  i j le {
    % swap a[i] a[j]
    a j a i get
    a i a j get 
    put put
    /i i 1 add def
    /j j 1 sub def
  } if
  i j gt {
    exit
  } if
} loop
i j
end } def

/subsort { 
8 dict begin
/R exch def
/L exch def
/a exch def
% x = a[(L+R)/2]
/x a L R add 2 idiv get def
a L R x partition
/j exch def
/i exch def
a L j
j L gt
a i R
i R lt
end
{ subsort }{ pop pop pop } ifelse
{ subsort }{ pop pop pop } ifelse
} def

end

/quicksort { qsortdict begin
dup length 1 gt {
% a
dup 
% a a 
length 1 sub 
% a n-1
0 exch subsort
} {
pop pop
} ifelse
end } def

% ----------------------------------------