#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_INTROSPECTIVE_SORT_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_INTROSPECTIVE_SORT_BASIC

#include "Insertion_sort_basic.h"

namespace Sorting_algorithms {
	namespace Introspective_sort {
		class Basic {
			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(4.0/3.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, int const bound ) {
					if ( c - a < use_insert ) {
						Sorting_algorithms::Insertion_sort::Basic::sort( array + a, c - a + 1 );
						return;
					}

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

					int b = (a + c)/2;
					Type pivot = array[b];
					array[b] = array[c];

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

					find_next_pair( array, pivot, a, c, lower, upper );

					while ( upper >= lower ) {
						swap( array, lower, upper );
						find_next_pair( array, pivot, a, c, 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 void find_next_pair( Type *const array, Type const &pivot, int a, int c, int &lower, int &upper ) {
					while ( lower < c && array[lower] < pivot ) {
						++lower;
					}

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

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

#endif