#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_ITERATIVE_MERGE_SORT_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_ITERATIVE_MERGE_SORT_ARRAY

#include "Insertion_sort_array.h"

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

					sort( array, tmp_array, n, use_insert );

					delete [] tmp_array;
				}

			private:
				template <typename Type>
				static void sort( Type *array, Type *tmp_array, int n, int use_insert ) { 
					int intervals = n/use_insert;

					for ( int i = 0; i < intervals; ++i ) {
						Insertion_sort::Basic::sort( array + i*use_insert, use_insert );
					}

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

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

						int remain = n % width;

						if ( remain > half_width ) {
							merge( array, tmp_array, intervals*width, intervals*width + half_width - 1, 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 = width/2;

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

						remain = n % width;

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

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

			private:
				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