Three implementations are provided:

• Pseudo code,
• A basic implemenation of the pseudo code, and
• An enhanced implementation.

When compiled with the -O2 option, the basic implementation sorts an array of size 200 million in 180 seconds while the enhanced implementation sorts the same list in 152 seconds.

Pseudo Code

To heap sort an array of size n:
	Convert the unsorted array into a max heap
	Convert the max heap into a sorted array
end

To convert an unsorted array of size n into a max heap:
	Starting at the middle (n/2) of the heap down to 1:
		Percolate the entry down to form a max heap
end

To convert a max heap of size n into a sorted array
	Starting from n down to 1:
		Decque the maximum place it in the last location
end

To percolating an entry down:
	Compare heap entry i with heap entries 2*i and 2*i + 1
		Swap entry i with the largest of the children
		and repeat with that child
	end
end

Basic Implementation

template <typename Type> void convert_to_max_heap( Type *const, int const );
template <typename Type> void convert_to_sorted_array( Type *const, int const );
template <typename Type> void percolate_down( Type *const, int, int const );
template <typename Type> void swap_and_update( Type *const, int &, int );

template <typename Type>
void heap_sort_basic( Type *const array, int const n ) {
    Type *const heap = array - 1;

    convert_to_max_heap( heap, n );
    convert_to_sorted_array( heap, n );
}

template <typename Type>
void convert_to_max_heap( Type *const heap, int const n ) {
    for ( int i = n/2; i >= 1; --i ) {
        percolate_down( heap, i, n );
    }
}

template <typename Type>
void convert_to_sorted_array( Type *const heap, int const n ) {
    for ( int i = n; i >= 2; --i ) {
        Type max = heap[1];
        heap[1] = heap[i];
        heap[i] = max;

        percolate_down( heap, 1, i - 1 );
    }
}

template <typename Type>
void percolate_down( Type *const heap, int posn, int const n ) {
    while ( 2*posn + 1 <= n ) {
        if ( heap[2*posn] > heap[2*posn + 1] && heap[2*posn] > heap[posn] ) {
            swap_and_update( heap, posn, 2*posn );
        } else if ( heap[2*posn + 1] > heap[posn] ) {
            swap_and_update( heap, posn, 2*posn + 1 );
        } else {
            return;
        }
    }

    if ( 2*posn == n && heap[2*posn] > heap[posn] ) {
        swap_and_update( heap, posn, 2*posn );
    }
}

template <typename Type>
void swap_and_update( Type *const array, int &i, int j ) {
    Type tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;

    i = j;
}

Enhanced Implementation on Arrays

This implementation:

• Unnecessary assignments in the percolations, and
• Bitwise operations for calculating 2*i and 2*i + 1.

This code should be compiled with the -O2 option.

template <typename Type> void convert_to_max_heap( Type *const, int const );
template <typename Type> void convert_to_sorted_array( Type *const, int const );
template <typename Type> void percolate_down( Type *const, int, int const );
int left( int const );
int right( int const posn );

template <typename Type>
void heap_sort( Type *const array, int const n ) {
    Type *const heap = array - 1;

    convert_to_max_heap( heap, n );
    convert_to_sorted_array( heap, n );
}

inline int left( int const posn ) {
    return (posn << 1);
}

inline int right( int const posn ) {
    return (posn << 1) | 1;
}

template <typename Type>
inline void convert_to_max_heap( Type *const heap, int const n ) {
    for ( int i = (n >> 1); i >= 1; --i ) {
        percolate_down( heap, i, n );
    }
}

template <typename Type>
inline void convert_to_sorted_array( Type *const heap, int const n ) {
    for ( int i = n; i >= 2; --i ) {
        Type max = heap[1];
        heap[1] = heap[i];
        heap[i] = max;

        percolate_down( heap, 1, i - 1 );
    }
}

template <typename Type>
inline void percolate_down( Type *const heap, int posn, int const n ) {
    Type tmp = heap[posn];

    while ( right( posn ) <= n ) {
        if ( heap[left( posn )] > heap[right( posn )] && heap[left( posn )] > tmp ) {
            heap[posn] = heap[left( posn )];
            posn = left( posn );
        } else if ( heap[right( posn )] > tmp ) {
            heap[posn] = heap[right( posn )];
            posn = right( posn );
        } else {
            heap[posn] = tmp;
            return;
        }
    }

    if ( left( posn ) == n && heap[left( posn )] > tmp ) {
        heap[posn] = heap[left( posn )];
        heap[left( posn )] = tmp;
    } else {
        heap[posn] = tmp;
    }
}