Shell sort

Shell sort (also called diminishing increment sort) was invented by Donald Shell. This sorting algorithm is a generalization of insertion sort. Insertion sort works efficiently on input that is already almost sorted.

In insertion sort, comparison happens between the adjacent elements. At most 1 inversion is eliminated for each comparison done with insertion sort. The variation used in shell sort is to avoid comparing elements until the last step of the algorithm. So, the last step of shell sort is to avoid comparing adjacent elements until the last step of the algorithm. So, the last step of shell sort is effectively the insertion sort algorithm. It improves insertion sort by allowing the comparison and exchange of elements that are far away. This is the first algorithm which got less than quadratic complexity among comparison sort algorithms.

Shell sort uses a sequence h1, h2, ….ht called the increment sequence. Any increment sequence is fine as long as h1 = 1 and some choices are better than others. Shell sort makes multiple passes through input list and sorts a number of equally sized sets using the insertion sort. Shell sort improves on the efficiency of insertion sort by quickly shifting values to their destination.

Here is an implementation of shell sort.

void shellSort(int arr[], int size)
{
	int i,j,h,v;
	
	for(h = 1;h = size/9;h = 3*h + 1);
	
	for( ; h > 0; h = h/3)
	{
		for(i = h + 1;i < size; i++)
		{
			v = arr[i];
			j = i;
			
			while(j>h && arr[j-h] > v)
			{
				arr[j] = arr[j-h];
				j -= h;
			}
			arr[j] = v;
		}
	}
	
}

Note that when h == 1, the algorithm makes a pass over the entire list, comparing adjacent element, but doing very few element exchanges. For h == 1, shell sort works like insertion sort, except the number of inversions that have to be eliminated is greatly reduced by the previous steps of the algorithm with h > 1.

Analysis

Shell sort is efficient algorithm for medium size lists. For bigger lists, the algorithm is not the best choice. Fastest of all O(n²) sorting algorithms.

Disadvantage of shell sort is that: it is complex and not nearly as efficient as the merge, heap and quick sorts. Shell sort is significantly slower that merge, heap and quick sorts, but it is relatively simple algorithm which makes it a great choice for sorting lists of less than 5000 items unless speed is important. It is also a good choice for repetitive sorting of smaller lists.

The best case of shell sort is when the array is already sorted in the right order. The number of comparisons is less. Running time of shell sort depends on the choice of increment sequence.