Shell Sort: Insertion Sort but Better

The insertion sort performs acceptably when the data is mostly sorted, but it can exhibit quadratic complexity in the worst-case when data is entirely unsorted. This is primarily because data must travel one element at a time, leading to bottlenecks when an element is far from its destination.

The shell sort substantially improves upon the insertion sort by tackling this core deficiency. Namely, it allows elements to cover great distances in a single swap. The full implementation follows.

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;
	}
}

Initially, we define a shell variable. Not very descriptive, admittedly. But think of the shell as the step size. In a typical insertion sort, we look one entry back to see if it is greater than our current entry, swapping as necessary, and keep doing this until the entry is in place. Our step size in this case is 1.

The exchange method can be found in a previous post.

In our code above, we increase the step size by a factor of 3 until it hits the upper bound of list.size(). Then, we work backwards through the list, swapping out-of-order elements as we go, but with our calculated step size instead of 1. Consider a situation where we have the following list, and a step size of 13.

13 1 2 3 4 5 6 7 8 9 10 11 12 0 14
^-----------------------------^

Using our step size, we will end up comparing 0 and 13 in the first pass and swapping just those elements. In doing so, we saved ourselves tens of swaps to get 0 and 13 in the right place. This is what makes shell sort so efficient.

We continue on in this fashion, decreasing the shell on every loop until it reaches 1, at which point it devolves into standard insertion sort. The difference is that the higher shell passes have put the list into mostly sorted order in an efficient manner, allowing insertion sort to shine.

Shell sort performs significantly better than insertion sort, though exact performance characteristics are hard to define. In the best case, it can perform in linearithmic time (O(nlg(n)), but worst case performance is dependent on the step size. As with previous sorts we have discussed, shell sort exhibits constant space complexity in the form of a few counters.