%!

/sortdict 16 dict def

sortdict begin

% args: 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

% args: a L R
% effect: sorts a[L .. R] 

/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
  % put recursion arguments on the stack
  % as well as the arguments for the tests
  a L j
  j L gt
  a i R
  i R lt
end
  { subsort }{ 
    % get rid of unused arguments
    pop pop pop 
  } ifelse
  { subsort }{ pop pop pop } ifelse
} def

% args: a
% effect: sorts the array a 

end

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

/bubblesort { 4 dict begin
/a exch def
/n a length 1 sub def
n 0 gt {
  n {
    0 1 n 1 sub {
      /i exch def
      a i get a i 1 add get gt {
        % if a[i] > a[i+1] swap a[i] and a[i+1]
      	a i 1 add 
      	a i get 
      	a i a i 1 add get 
      	% set new a[i] = old a[i+1]
      	put 
      	% set new a[i+1] = old a[i]
   	put
      } if
    } for
    /n n 1 sub def
  } repeat
} if
end } def

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