#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SHELL_SORT_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_SHELL_SORT_BASIC

namespace Sorting_algorithms {
	namespace Shell_sort {
		class Basic {
			public:
				template <typename Type>
				static void sort( Type *array, int n ) {
					for ( int i = n/2; i >= 1; i /= 2 ) {
						for ( int j = i; j < n; ++j ) {
							for ( int k = j - i; k >= 0; k -= i ) {
								if ( array[k] > array[k + i] ) {
									swap( array, k, k + i );
								} else {
									break;
								}
							}
						}
					}
				}

			private:
				template <typename Type>
				static void swap( Type *array, int i, int j ) {
					Type tmp = array[i];
					array[i] = array[j];
					array[j] = tmp;
				}
		};
	}
}

#endif