#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_INSERTION_SORT_POINTER
#define CA_UWATERLOO_ALUMNI_DWHARDER_INSERTION_SORT_POINTER

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

				template <typename Type>
				static void sort( Type *const lower, Type *const upper ) {
					for ( Type *forward = lower + 1; forward <= upper; ++forward ) {
						Type tmp = *forward;

						for ( Type *back_0 = forward - 1, *back_1 = forward; back_0 >= lower; ) {
							if ( *back_0 > tmp ) {
								*(back_1--) = *(back_0--);
							} else {
								*back_1 = tmp;
								goto object_placed;
							}
						}

						*lower = tmp;

						object_placed: ;
					}
				}
		};
	}
}

#endif