#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BINARY_RADIX_SORT_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_BINARY_RADIX_SORT_ARRAY

namespace Sorting_algorithms {
	namespace Binary_radix_sort {
		class Array {
			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];

					int tail_0 = 0;
					int tail_1 = n - 1;

					for ( int i = 0; i < n; ++i ) {
						if ( array[i] & 1 ) {
							tmp_array[tail_1] = array[i];
							--tail_1;
						} else {
							tmp_array[tail_0] = array[i];
							++tail_0;
						}
					}

					int count_0 = tail_0;
					int i = 1;
					int mask = 1;

					while ( true ) {
						if ( i == bits ) {
							break;
						}

						mask <<= 1;

						count_0 = binary_radix_sort_internal( tmp_array, array, count_0, n, mask );

						++i;

						if ( i == bits ) {
							break;
						}

						mask <<= 1;

						count_0 = binary_radix_sort_internal( array, tmp_array, count_0, n, mask );

						++i;
					}

					if ( bits & 1 ) {
						int i = 0;

						for ( int j = 0; j < count_0; ++i, ++j ) {
							array[i] = tmp_array[j];
						}

						for ( int j = n - 1; j >= count_0; ++i, --j ) {
							array[i] = tmp_array[j];
						}
					} else {
						for ( int i = count_0, j = n - 1; i < j; ++i, --j ) {
							Type tmp = array[i];
							array[i] = array[j];
							array[j] = 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 int binary_radix_sort_internal( Type *const in_array, Type *const out_array, int count_0, int const n, int const mask ) {
					int tail_0 = 0;
					int tail_1 = n - 1;

					for ( int i = 0; i < count_0; ++i ) {
						if ( in_array[i] & mask ) {
							out_array[tail_1] = in_array[i];
							--tail_1;
						} else {
							out_array[tail_0] = in_array[i];
							++tail_0;
						}
					}

					for ( int i = n - 1; i >= count_0; --i ) {
						if ( in_array[i] & mask ) {
							out_array[tail_1] = in_array[i];
							--tail_1;
						} else {
							out_array[tail_0] = in_array[i];
							++tail_0;
						}
					}

					return tail_0;
				}
		};
	}
}

#endif