#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_STOOGE_SORT_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_STOOGE_SORT_BASIC

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

				template <typename Type>
				static void sort( Type * array, int lower, int upper ) {
					if ( lower == upper ) {
						return;
					}

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

					if ( lower + 1 == upper ) {
						return;
					}

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

					sort( array, lower,         upper - third );
					sort( array, lower + third, upper         );
					sort( array, lower,         upper - third );
				}

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

#endif