#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BINARY_RADIX_SORT_POINTER
#define CA_UWATERLOO_ALUMNI_DWHARDER_BINARY_RADIX_SORT_POINTER

namespace Sorting_algorithms {
	namespace Binary_radix_sort {
		class Pointer {
			public:
				template <typename Type>
				static void sort( Type *const array, int const n, int const bits ) {
					if ( bits <= 0 ) {
						return;
					}

					Type *tmp_array = new Type[n];

					Type *count_0 = binary_radix_sort_internal_1( array, array + n - 1, tmp_array, tmp_array + n - 1, 1 << bits );

					if ( bits & 1 ) {
						Type *ptr_0 = array;

						for ( Type *ptr_1 = tmp_array;         ptr_1 <  count_0; ++ptr_0, ++ptr_1 ) {
							*ptr_0 = *ptr_1;
						}

						for ( Type *ptr_1 = tmp_array + n - 1; ptr_1 >= count_0; ++ptr_0, --ptr_1 ) {
							*ptr_0 = *ptr_1;
						}
					} else {
						for ( Type *ptr_0 = count_0, *ptr_1 = array + n - 1; ptr_0 < ptr_1; ++ptr_0, --ptr_1 ) {
							Type tmp = *ptr_0;
							*ptr_0 = *ptr_1;
							*ptr_1 = tmp;
						}
					}

					delete [] tmp_array;
				}

				template <typename Type>
				static void sort( Type *const array, int const lower, int const upper, int const bits ) {
					sort( array + lower, upper - lower + 1, bits );
				}

			private:
				template <typename Type>
				static Type *binary_radix_sort_internal_1( Type *const lower_0, Type *const upper_0, Type *const lower_1, Type *const upper_1, int const max_mask ) {
					Type *tail_0 = lower_1;
					Type *tail_1 = upper_1;

					for ( Type *ptr = lower_0; ptr <= upper_0; ++ptr ) {
						if ( *ptr & 1 ) {
							*(tail_1--) = *ptr;
						} else {
							*(tail_0++) = *ptr;
						}
					}

					Type *count_0 = tail_0;
					int mask = 1;

					while ( true ) {
						mask <<= 1;

						if ( mask == max_mask ) {
							return count_0;
						}

						count_0 = binary_radix_sort_internal_2( lower_1, upper_1, count_0, lower_0, upper_0, mask );

						mask <<= 1;

						if ( mask == max_mask ) {
							return count_0;
						}

						count_0 = binary_radix_sort_internal_2( lower_0, upper_0, count_0, lower_1, upper_1, mask );
					}
				}

				template <typename Type>
				static Type *binary_radix_sort_internal_2( Type *lower_0, Type *upper_0, Type *const count_0, Type *tail_0, Type *tail_1, int const mask ) {
					while ( lower_0 < count_0 ) {
						if ( *lower_0 & mask ) {
							*(tail_1--) = *(lower_0++);
						} else {
							*(tail_0++) = *(lower_0++);
						}
					}

					while ( upper_0 >= count_0 ) {
						if ( *upper_0 & mask ) {
							*(tail_1--) = *(upper_0--);
						} else {
							*(tail_0++) = *(upper_0--);
						}
					}

					return tail_0;
				}
		};
	}
}

#endif