#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_RECURSIVE_MERGE_SORT_POINTER
#define CA_UWATERLOO_ALUMNI_DWHARDER_RECURSIVE_MERGE_SORT_POINTER

#include "Insertion_sort_pointer.h"

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

					delete [] tmp_array;
				}
				
				template <typename Type>
				static void sort( Type *a, Type *const c, Type *tmp, int const use_insert = 16 ) {
					if ( a + use_insert > c ) {
						Sorting_algorithms::Insertion_sort::Pointer::sort( a, c );
						return;
					}
			
					Type *b = a + (c - a)/2;
			
					sort( a,     b, tmp, use_insert );
					sort( b + 1, c, tmp, use_insert );
			
					merge( tmp, a, b, c );
			
					for ( ; a <= c; ++a, ++tmp ) {
						*a = *tmp;
					}
				}
			
				template <typename Type>
				inline static void merge( Type *out, Type * a, Type *const b, Type *const d ) {
					Type *c = b + 1;
			
					while ( a <= b && c <= d ) {
						if ( *a < *c ) {
							*(out++) = *(a++);
						} else {
							*(out++) = *(c++);
						}
					}
			
					while ( a <= b ) {
						*(out++) = *(a++);
					}
			
					while ( c <= d ) {
						*(out++) = *(c++);
					}
				}
		};
	}
}
				
#endif