#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BIDIRECTIONAL_BUBBLE_SORT_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_BIDIRECTIONAL_BUBBLE_SORT_ARRAY

namespace Sorting_algorithms {
	namespace Bidirectional_bubble_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 lower, int upper ) {
					while ( true ) {
						upper = bubble_up( array, lower, upper );

						if ( lower == upper ) {
							break;
						}

						lower = bubble_down( array, lower, upper );

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

				template <typename Type>
				inline static int bubble_up( Type *const array, int const lower, int const upper ) {
					Type max = array[lower];
					int new_upper = lower;

					for ( int i = lower + 1; i <= upper; ++i ) {
						if ( array[i] < max ) {
							array[i - 1] = array[i];
							new_upper = i - 1;
						} else {
							array[i - 1] = max;
							max = array[i];
						}
					}

					array[upper] = max;

					return new_upper;
				}

				template <typename Type>
				inline static int bubble_down( Type *const array, int const lower, int const upper ) {
					Type min = array[upper];
					int new_lower = upper;

					for ( int i = upper - 1; i >= lower; --i ) {
						if ( array[i] > min ) {
							array[i + 1] = array[i];
							new_lower = i + 1;
						} else {
							array[i + 1] = min;
							min = array[i];
						}
					}

					array[lower] = min;

					return new_lower;
				}
		};
	}
}

#endif