#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BUBBLE_SORT_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_BUBBLE_SORT_ARRAY

namespace Sorting_algorithms {
	namespace 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 const a, int const b ) {
					int i = b;

					while ( i > a ) {
						i = bubble_up( array, a, i );
					}
				}

				template <typename Type>
				inline static int bubble_up( Type *const array, int const a, int const i ) {
					Type max = array[a];
					int next_i = a;

					for ( int j = a + 1; j <= i; ++j ) {
						if ( array[j] < max ) {
							array[j - 1] = array[j];
							next_i = j - 1;
						} else {
							array[j - 1] = max;
							max = array[j];
						}
					}

					array[i] = max;

					return next_i;
				}
		};
	}
}

#endif