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
|
|
Fast | Slow |
Input size: |