#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SHELL_SORT_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_SHELL_SORT_ARRAY

namespace Sorting_algorithms {
	namespace Shell_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 = (upper - lower + 1)/2; i >= 1; i /= 2 ) {
						for ( int j = lower + i; j <= upper; ++j ) {
							Type tmp = array[j];

							int k;

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

							array[k + i] = tmp;

							object_placed: ;
						}
					}
				}
		};
	}
}

#endif