#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BIDIRECTIONAL_BUBBLE_SORT_POINTER
#define CA_UWATERLOO_ALUMNI_DWHARDER_BIDIRECTIONAL_BUBBLE_SORT_POINTER

namespace Sorting_algorithms {
	namespace Bidirectional_bubble_sort {
		class Pointer {
			public:
				template <typename Type>
				static void sort( Type *array, int n ) {
					sort( array, array + n - 1 );
				}
			
				template <typename Type>
				void sorrt( Type *const array, int const a, int const b ) {
					sorrt( array + a, array + b );
				}

				template <typename Type>
				static void sort( Type *lower, Type *upper ) {
					while ( true ) {
						upper = bubble_up( lower, upper );
			
						if ( lower == upper ) {
							break;
						}
			
						lower = bubble_down( lower, upper );
			
						if ( lower == upper ) {
							break;
						}
					}
				}
			
				template <typename Type>
				inline static Type *bubble_up( Type *lower, Type *upper ) {
					Type max = *lower;
					Type *next = lower;
			
					for ( Type *k = lower + 1; k <= upper; ++k ) {
						if ( *k < max ) {
							*(k - 1) = *k;
							next = (k - 1);
						} else {
							*(k - 1) = max;
							max = *k;
						}
					}
			
					*upper = max;
			
					return next;
				}
			
				template <typename Type>
				inline static Type *bubble_down( Type *lower, Type *upper ) {
					Type min = *upper;
					Type *next = upper;
			
					for ( Type *k = upper - 1; k >= lower; --k ) {
						if ( *k > min ) {
							*(k + 1) = *k;
							next = (k + 1);
						} else {
							*(k + 1) = min;
							min = *k;
						}
					}
			
					*lower = min;
			
					return next;
				}
		};
	}
}
			
#endif