%
% heapsort by Owen Densmore at Sun Microsystems, Inc.
%
/SiftDown { % L U => -
    /U exch def
    /L exch def
    /Xl X L get def
    {	L 2 mul 1 add			% C (i.e child index)
    	dup U gt {pop exit} if
    	X 1 index get			% C Xc
    	1 index 1 add			% C Xc C+1
    	
    	dup U le {
    	    X 1 index get		% C Xc C+1 Xc+1
	    dup 3 index Bigger? {4 2 roll} if
    	    pop pop			% C' Xc' (largest child)
    	} {pop} ifelse
    	
    	Xl 1 index Bigger? {pop pop exit} if
    	X L 3 -1 roll put
    	/L exch def
    } loop
    X L Xl put
} def
/heapsort { % array proc => array (sorted)
10 dict begin
    /Bigger? exch cvx def		% a b bigger? => t if a>b
    /X exch def
    
    % Make the heap
    X dup length 1 sub			% X N
    dup 1 sub 2 div floor -1 0 {	% X N for: |N/2| -1 0
	1 index SiftDown
    } for				% X N
    
    % Sort the heap
    -1 1 {				% X i:N -1 1
        2 copy 1 index 0		% X i X i X 0
        4 copy get 3 1 roll get exch	% X i X i X 0 Xi X0
        4 1 roll put put		% X i

        0 exch 1 sub SiftDown
    } for
end
} def