#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BINARY_RADIX_SORT_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_BINARY_RADIX_SORT_BASIC

namespace Sorting_algorithms {
	namespace Binary_radix_sort {
		class Basic {
			public:
				template <typename Type>
				static void sort( Type *const array, int const n, int const bits ) {
					Type *queue_0 = new Type[n];
					Type *queue_1 = new Type[n];

					for ( int i = 0, mask = 1; i < bits; ++i, mask <<= 1 ) {
						int tail_0 = 0;
						int tail_1 = 0;

						for ( int i = 0; i < n; ++i ) {
							if ( (array[i] & mask) == 0 ) {
								queue_0[tail_0] = array[i];
								++tail_0;
							} else {
								queue_1[tail_1] = array[i];
								++tail_1;
							}
						}

						int i = 0;

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

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

					delete [] queue_0;
					delete [] queue_1;
				}
		};
	}
}

#endif