#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_RECURSIVE_MERGE_SORT_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_RECURSIVE_MERGE_SORT_BASIC

#include "Insertion_sort_basic.h"

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

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

					delete [] tmp_array;
				}

				template <typename Type>
				static void sort( Type *array, Type *tmp_array, int a, int c, int use_insert = 16 ) { 
					if ( c - a < use_insert ) {
						Sorting_algorithms::Insertion_sort::Basic::sort( array + a, c - a + 1 );
						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];
					}
				}

			private:
				template <typename Type>
				static void merge( Type *in_array, Type *out_array, int a, int b, int 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