Shell sort (opens new window), also known as the diminishing increment sort, is one of the oldest sorting algorithms, named after its inventor Donald. L. Shell (opens new window) (1959). It is fast, easy to understand and easy to implement. However, its complexity analysis is a little more sophisticated.

The idea of Shell sort is the following:

1. Arrange the data sequence in a two-dimensional array
2. Sort the columns of the array

Shell sort improves insertion sort. It starts by comparing elements far apart, then elements less far apart, and finally comparing adjacent elements (effectively an insertion sort).

The effect is that the data sequence is partially sorted. The process above is repeated, but each time with a narrower array, i.e. with a smaller number of columns. In the last step, the array consists of only one column.

Example of Shell sort:

(opens new window)

Pseudo code for Shell Sort:

input
foreach element in input
{
    for(i = gap; i < n; i++)
    {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        a[j] = temp
    }
}

Auxiliary Space: O(n) total, O(1) auxiliary
Time Complexity: O(nlogn)