#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_HEAP_SORT_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_HEAP_SORT_ARRAY

namespace Sorting_algorithms {
	namespace Heap_sort {
		class Array {
			public:
				template <typename Type>
				static void sort( 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>
				static void sort( Type *const array, int const lower, int const upper ) {
					Type *const heap = array + lower - 1;

					convert_to_max_heap( heap, upper - lower + 1 );
					convert_to_sorted_array( heap, upper - lower + 1 );
				}

				// return 2*posn
				inline static int left( int const posn ) {
					return (posn << 1);
				}

				// return 2*posn + 1
				inline static int right( int const posn ) {
					return (posn << 1) | 1;
				}

				template <typename Type>
				inline static 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 static void convert_to_sorted_array( Type *const heap, int const n ) {
					// Create the Sorted Array
					// Dequeue the maximum element and place it into the ith location
					for ( int i = n; i >= 2; --i ) {
						// Swap the first and last entries of the heap
						Type max = heap[1];
						heap[1] = heap[i];
						heap[i] = max;

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

				template <typename Type>
				inline static 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 ) {
							// The left child is the largest of the current node and its children
							heap[posn] = heap[left( posn )];
							posn = left( posn );
						} else if ( heap[right( posn )] > tmp ) {
							heap[posn] = heap[right( posn )];
							posn = right( posn );
						} else {
							// The current node is larger than either child--stop
							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;
					}
				}
		};
	}
}

#endif