Shellsort

Shellsort is a variation of insertion sort (invented by Donald Shell) in which we use insertion sort repeatedly on evenly spaced subsequences of elements, decreasing the spacing each time until we end up with ordinary insertion sort (this technique is thus also called diminishing increment sort). The intuition is that by starting by sorting widely spaced elements, we can reduce the number of inversions much more quickly than ordinary insertion sort, so that each of the subsequent insertion sorts can go faster.

To sort with an increment of k means to sort items 0, k, 2k,…; then items 1, k+1, 2k+1,…; then 2, k+2,…; etc. up to the subsequence starting with item k-1. Although any sequence that ends with an increment of 1 will produce correct results, certain sequences are better than others. The sequence =2p-1, 2p-1-1,…,1, where p=⌊lg N⌋, results in an overall running time of O(N3/2), which is significantly better than the worst case for plain insertion sorting. In the demo below, the subsequence being insertion-sorted at any given is marked with "V" characters.

Fast Slow
Input size:
Initial array: Array: Inversion count: # comparisons: