#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_RECURSIVE_MERGE_SORT_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_RECURSIVE_MERGE_SORT_ARRAY

#include "Insertion_sort_array.h"

namespace Sorting_algorithms {
	namespace Recursive_merge_sort {
		class Array {
			public:
				template <typename Type>
				static void sort( Type *const array, int const n ) {
					Type *tmp_array = new Type[n];

					sort( array, tmp_array, 0, n - 1 );

					delete [] tmp_array;
				}

				template <typename Type>
				static void sort( Type *const array, Type *const tmp_array, int const a, int const c, int const use_insert = 16 ) { 
					if ( c - a < use_insert ) {
						Sorting_algorithms::Insertion_sort::Array::sort( array, a, c );
						return;
					}

					int b = (a + c)/2;

					sort( array, tmp_array, a,     b, use_insert );
					sort( array, tmp_array, b + 1, c, use_insert );

					merge( array, tmp_array, a, b, c );

					for ( int i = a; i <= c; ++i ) {
						array[i] = tmp_array[i];
					}
				}

				template <typename Type>
				inline static void merge( Type *const in_array, Type *const out_array, int const a, int const b, int const d ) {
					int out = a;
					int lower = a;
					int upper = b + 1;

					while ( lower <= b && upper <= d ) {
						if ( in_array[lower] < in_array[upper] ) {
							out_array[out] = in_array[lower];
							++lower;
						} else {
							out_array[out] = in_array[upper];
							++upper;
						}

						++out;
					}

					for ( ; lower <= b; ++lower, ++out ) {
						out_array[out] = in_array[lower];
					}

					for ( ; upper <= d; ++upper, ++out ) {
						out_array[out] = in_array[upper];
					}
				}
		};
	}
}

#endif