#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_QUICK_SORT_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_QUICK_SORT_ARRAY

#include "Insertion_sort_array.h"

namespace Sorting_algorithms {
	namespace Quick_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 = 45 ) {
					if ( c - a < use_insert ) {
						Insertion_sort::Array::sort( array, a, c );
						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;

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

				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