#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_INTROSPECTIVE_SORT_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_INTROSPECTIVE_SORT_ARRAY

#include "Insertion_sort_array.h"

namespace Sorting_algorithms {
	namespace Introspective_sort {
		class Array {
			public:
				template <typename Type>
				static void sort( Type *const array, int const n ) {
					sort( array, 0, n - 1 );
				}

				template <typename Type>
				static void sort( Type *const array, int const a, int const c, int const use_insert = 72 ) {
					if ( c - a < use_insert ) {
						Insertion_sort::Basic::sort( array + a, c - a + 1 );
						return;
					}

					int bound = std::ceil( ( std::log( static_cast<double>( n )) - log( static_cast<double>( use_insert ) ) )/std::log(16.0/11.0) );

					recursive( array, a, c, use_insert, bound );
				}

			private:
				template <typename Type>
				static void recursive( Type *const array, int const a, int const c, int const use_insert = 45 ) {
					if ( c - a < use_insert ) {
						Insertion_sort::Array::sort( array, a, c );
						return;
					}

					if ( bound == 0 ) {
						Sorting_algorithms::Heap_sort::Basic::sort( array + a, c - a + 1 );
						return;
					}

					Type pivot;

					select_pivot( array, pivot, a, (a + c)/2, c );

					int lower = a + 1;
					int upper = c - 1;

					find_next_pair( array, pivot, lower, upper );

					while ( upper >= lower ) {
						swap( array, lower, upper );
						find_next_pair( array, pivot, lower, upper );
					}

					array[c] = array[lower];
					array[lower] = pivot;

					recursive( array, a,         upper, use_insert, bound - 1 );
					recursive( array, lower + 1, c,     use_insert, bound - 1 );
				}

				template <typename Type>
				static inline void select_pivot( Type *const array, Type &pivot, int a, int b, int c ) {
					if ( array[a] < array[b] ) {
						if ( array[b] < array[c] ) {
							// Case: a < b < c
							pivot = array[b];
							array[b] = array[c];
						} else {
							if ( array[a] < array[c] ) {
								// Case: a < c < b
								pivot = array[c];
							} else {
								// Case: c < a < b
								pivot = array[a];
								array[a] = array[c];
							}
						}
					} else {
						if ( array[b] < array[c] ) {
							if ( array[a] < array[c] ) {
								// Case: b < a < c
								pivot = array[a];
								array[a] = array[b];
								array[b] = array[c];
							} else {
								// Case: b < c < a
								pivot = array[c];
								Type tmp = array[a];
								array[a] = array[b];
								array[b] = tmp;
							}
						} else {
							// Case: c < b < a
							pivot = array[b];
							array[b] = array[a];
							array[a] = array[c];
						}
					}

				}

				template <typename Type>
				static inline void find_next_pair( Type *const array, Type const &pivot, int &lower, int &upper ) {
					while ( array[lower] < pivot ) {
						++lower;
					}

					while ( array[upper] > pivot ) {
						--upper;
					}
				}

				template <typename Type>
				static inline void swap( Type *const array, int const a, int const b ) {
					Type tmp = array[a];
					array[a] = array[b];
					array[b] = tmp;
				}
		};
	}
}

#endif