#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_INTROSPECTIVE_SORT_POINTER
#define CA_UWATERLOO_ALUMNI_DWHARDER_INTROSPECTIVE_SORT_POINTER

#include "Insertion_sort_pointer.h"

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

				template <typename Type>
				static void sort( Type *const a, Type *const c, int const use_insert = 45 ) {
					if ( a + use_insert > c ) {
						Insertion_sort::Pointer::sort( a, c );
						return;
					}

					Type pivot;

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

					Type *lower = a;
					Type *upper = c;

					while ( *(++lower) < pivot );
					while ( *(--upper) > pivot );

					while ( upper >= lower ) {
						swap( lower, upper );
						while ( *(++lower) < pivot );
						while ( *(--upper) > pivot );
					}

					*c = *lower;
					*lower = pivot;

					sort( a, upper, use_insert );
					sort( lower + 1, c, use_insert );
				}

				template <typename Type>
				static inline void select_pivot( Type &pivot, Type *a, Type *b, Type *c ) {
					if ( *a < *b ) {
						if ( *b < *c ) {
							pivot = *b;
							*b = *c;
						} else {
							if ( *a < *c ) {
								pivot = *c;
							} else {
								pivot = *a;
								*a = *c;
							}
						}
					} else {
						if ( *b < *c ) {
							if ( *a < *c ) {
								pivot = *a;
								*a = *b;
								*b = *c;
							} else {
								pivot = *a;
								*a = *b;
								*b = pivot;
								pivot = *c;
							}
						} else {
							pivot = *b;
							*b = *a;
							*a = *c;
						}
					}

				}

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

#endif