#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_RADIX_SORT_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_RADIX_SORT_BASIC

#include <iostream>
using namespace std;

namespace Sorting_algorithms {
	namespace Radix_sort {
		class Basic {
			public:
				template <typename Type>
				static void sort( Type *const array, int const n, int const digits, int const base = 10 ) {
					int *queue = new int[digits];
					Type *tmp_array = new Type[n];

					for ( int i = 0, divisor = 1; i < digits; ++i, divisor *= base ) {
						for ( int j = 0; j < digits; ++j ) {
							queue[j] = 0;
						}

						for ( int j = 0; j < n; ++j ) {
							++( queue[(array[j] / divisor) % digits] );
						}

						for ( int j = 1; j < digits; ++j ) {
							queue[j] += queue[j - 1];
						}

						for ( int j = 0; j < n; ++j ) {
							int entry = (array[j] / divisor) % digits;

							tmp_array[queue[entry]] = array[j];
							++( queue[entry] );
						}

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

//					delete [] queue;
//					delete [] tmp_array;
				}
		};
	}
}

#endif