Listing 3 (hsort.cpp)

//       HSort.Cpp  V.2.0 - 2/27/91
//
//  Turbo C++ V.1.0
//
//  Michael Kelly - Author
//
//  Sorts an array of "Things" in place using
//  the HeapSort Algorithm.
//
#include "hsort.hpp"

static Thing tmp;       // temporary for swaps

//  Exchange two Things.
//
inline void swap( Thing &t1, Thing &t2 )
{
    tmp = t2;
    t2 = t1;
    t1 = tmp;
}

// Sift down through the heap.
//
void sift_heap( size_t N, size_t root_node, Thing *ptr)
{
    size_t parent = root_node, child = root_node << 1;

    do  {

   if( child > N )
      break;

   if(child != N &&
       ( ptr[ child ] < ptr[ child + 1 ] ))
      ++child;

   if( ! ( ptr[ parent ] < ptr[ child ] ))
      break;
   else  {
      swap( ptr[ child ], ptr[ parent ] );
      child = ( parent = child ) << 1;
   }

    }while( 1 );
}

// classic HeapSort Algorithm
//
void heapsort( size_t num_things, Thing *array )
{
    size_t root = num_things >> 1;

    if( num_things < 2 || !array )
   return;

    array;  // allows indexing array from 1..N

    for( ; root > 1; --root )
   sift_heap( num_things, root, array );

    for( ; num_things > 1; --num_things ) {
   sift heap( num_things, 1, array );
   swap( array[ num_things ], array[ 1 ] );
    }

    // "erase" tmp's "shallow copy"
    // so tmp's destructor won't
    // deallocate memory owned
    // by another Thing
    //
    tmp = TheNullThing;
}

// End of File