#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_INSERTION_SORT_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_INSERTION_SORT_ARRAY

namespace Sorting_algorithms {
	namespace Insertion_sort {
		class Array {
			public:
				template <typename Type>
				static void sort( Type *const array, int const n ) {
					sort( array, 0, n - 1 );
				}

				template <typename Type>
				static void sort( Type *const array, int const lower, int const upper ) {
					for ( int i = lower + 1; i <= upper; ++i ) {
						Type tmp = array[i];

						for ( int j = i - 1; j >= lower; --j ) {
							if ( array[j] > tmp ) {
								array[j + 1] = array[j];
							} else {
								array[j + 1] = tmp;
								goto object_placed;
							}
						}

						array[lower] = tmp;

						object_placed: ;
					}
				}
		};
	}
}

#endif