#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_STOOGE_SORT_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_STOOGE_SORT_ARRAY

namespace Sorting_algorithms {
	namespace Stooge_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 bool sort( Type *const array, int const lower, int const upper ) {
					if ( upper - lower <= 1 ) {
						if ( array[lower] > array[upper] ) {
							swap( array, lower, upper );
							return false;
						} else {
							return true;
						}
					}

					if ( array[lower] > array[upper] ) {
						swap( array, lower, upper );
					}

					int third = (upper - lower + 1)/3;

					bool unchanged = sort( array, lower, upper - third );

					if ( sort( array, lower + third, upper ) && unchanged ) {
						return unchanged;
					} else {
						sort( array, lower, upper - third );
						return false;
					}
				}

			private:
				template <typename Type>
				static void swap( Type *const array, int i, int j ) {
					Type tmp = array[i];
					array[i] = array[j];
					array[j] = tmp;
				}
		};
	}
}

#endif