/* Program to sort numbers using heapsort */
Parse Arg N
If N="" then Do
   Say "How many numbers would you like sorted?"
   Parse Pull N
End
Do i=1 to N
   Stem.i=Random(0,N)
End
Stem.0=N
et=HeapSort()

/* Uncomment to print the numbers to the screen after sort 
Do i=1 to N
  Say Stem.i
End
*/

Say "Heapsort took" et "seconds"
Exit

 /* ------------------------------------------------------------------ */
 /* function: heap sort routine                                        */
 /*                                                                    */
 /* call:     HeapSort                                                 */
 /*                                                                    */
 /* returns:  nothing                                                  */
 /*                                                                    */
 /* notes:    You must save the elements to sort in the stem "STEM."   */
 /*           stem.0 must contain the number of elements in the stem.  */
 /*                                                                    */
 /* reference: Sedgewick, "Algorithms"                                 */
 /*                                                                    */
 Heapsort: PROCEDURE expose stem.
   start=Time("R")

   M = stem.0
   N = M
 
   do k=M % 2 to 1 by -1
     call DownHeap k N
   end /* do */
 
   do while N>1
     t = stem.1
     stem.1 = stem.n
     stem.n = t
     n = n-1
     call DownHeap 1 N
   end /* do */
   end=time("R")
   elapsed=end-start
 RETURN elapsed
 
 /* subroutine of HeapSort                                             */
 DownHeap: PROCEDURE expose stem.
   parse Arg k N
 
   v = stem.k
 
   do while k <= N%2
     j = k+k
     if j < n then
     do
       i = j+1
       if stem.j < stem.i then
         j=j+1
     end  /* do */
 
     if v >= stem.j then
       signal label
 
     stem.k = stem.j
     k = j
   end /* do */
 
 Label:
   stem.k = v
 RETURN