#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BUCKET_SORT_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_BUCKET_SORT_ARRAY

namespace Sorting_algorithms {
	namespace Bucket_sort {
		class Array {
			public:
				static void sort( int *const array, int const n, int const m ) {
					sort( array, 0, n - 1, m );
				}

				static void sort( int *array, int lower, int upper, int const m ) {
					int *bucket = new int[m];

					for ( int i = 0; i < m; ++i ) {
						bucket[i] = 0;
					}

					for ( int i = lower; i <= upper; ++i ) {
						++( bucket[array[i]] );
					}

					for ( int i = 0; i < m; ++i ) {
						for ( int j = 0; j < bucket[i]; ++j ) {
							array[lower] = i;
							++lower;
						}
					}

					delete [] bucket;
				}
		};
	}
}

#endif