#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BIDIRECTIONAL_BUBBLE_SORT_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_BIDIRECTIONAL_BUBBLE_SORT_BASIC

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

					while ( true ) {
						for ( int j = lower; j < upper; ++j ) {
							if ( array[j] > array[j + 1] ) {
								swap( array, j, j + 1 );
							}
						}

						--upper;

						if ( lower == upper ) {
							return;
						}

						for ( int j = upper; j > lower; --j ) {
							if ( array[j] < array[j - 1] ) {
								swap( array, j, j - 1 );
							}
						}

						++lower;

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

			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