#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_ITERATIVE_MERGE_SORT_POINTER
#define CA_UWATERLOO_ALUMNI_DWHARDER_ITERATIVE_MERGE_SORT_POINTER

#include "Insertion_sort_pointer.h"

namespace Sorting_algorithms {
	namespace Iterative_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 ) {
					int tmp_array[n];

					int intervals = n/use_insert;

					for ( int i = 0; i < intervals; ++i ) {
						insertion_sort_internal( array + i*use_insert, array + (i + 1)*use_insert - 1 );
					}

					insertion_sort_internal( array + intervals*use_insert, array + n - 1 );

					for ( int width = 2*use_insert; true; width *= 2 ) {
						intervals = n/width;
						int half = width/2;

						for ( int i = 0; i < intervals; ++i ) {
							merge( tmp_array + i*width, array + i*width, array + i*width + half - 1, array + (i + 1)*width - 1 );
						}

						int remain = n % width;

						if ( remain > half ) {
							merge( tmp_array + intervals*width, array + intervals*width, array + intervals*width + half - 1, array + n - 1 );
						} else {
							for ( int i = width*intervals; i < n; ++i ) {
								tmp_array[i] = array[i];
							}
						}

						if ( width > n ) {
							for ( int i = 0; i < n; ++i ) {
								array[i] = tmp_array[i];
							}

							break;
						}

						width *= 2;

						intervals = n/width;
						half = width/2;

						for ( int i = 0; i < intervals; ++i ) {
							merge( array + i*width, tmp_array + i*width, tmp_array + i*width + half - 1, tmp_array + (i + 1)*width - 1 );
						}

						remain = n % width;

						if ( remain > half ) {
							merge( array + intervals*width, tmp_array + intervals*width, tmp_array + intervals*width + half - 1, tmp_array + n - 1 );
						} else {
							for ( int i = width*intervals; i < n; ++i ) {
								array[i] = tmp_array[i];
							}
						}

						if ( width > n ) {
							break;
						}
					}
				}

				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