shell-sort.h

template<typename T>
void exchange(vector<T>& list, int i, int j)
{
	T temp = list[i];
	list[i] = list[j];
	list[j] = temp;
}

/**
 * Part of the drawback of the insertion sort
 * is that it performs poorly when elements need to travel
 * far, because the travel must occur one step at a time.
 * In the worst case, the smallest item will need to be
 * moved from the end of the list to the beginning.
 * The shellsort aims to remedy this by creating larger
 * jumps for each item. It proceeds by establishing a
 * shell size, and following standard insertion sort protocol
 * for switching bigger items with smaller items.
 * By the time the shell size is 1, the list should be mostly
 * in order, reducing the time complexity substantially,
 * though its precise performance is difficult to quantify.
 */
template<typename T>
void shell_sort(vector<T>& list)
{
	int shell = 0;
	while (shell < list.size())
	{
		shell = (shell * 3) + 1;
	}

	while (shell > 0)
	{
		for (int i = shell; i < list.size(); ++i)
		{
			for (int j = i; j > 0 && list[j] < list[j - shell]; j -= shell)
			{
				exchange(list, j, j - shell);
			}
		}
		
		shell /= 3;
	}
}