Shell Sort

The principle of Shell sort is to rearrange the file so that looking at every hth element yields a sorted file. We call such a file h-sorted. If the file is then k-sorted for some other integer k, then the file remains h-sorted. For instance, if a list was 5-sorted and then 3-sorted, the list is now not only 3-sorted, but both 5- and 3-sorted. If this were not true, the algorithm would undo work that it had done in previous iterations, and would not achieve such a low running time.


The algorithm draws upon a sequence of positive integers known as the increment sequence. Any sequence will do, as long as it ends with 1, but some sequences perform better than others. The algorithm begins by performing a gap insertion sort, with the gap being the first number in the increment sequence. It continues to perform a gap insertion sort for each number in the sequence, until it finishes with a gap of 1. When the increment reaches 1, the gap insertion sort is simply an ordinary insertion sort, guaranteeing that the final list is sorted. Beginning with large increments allows elements in the file to move quickly towards their final positions, and makes it easier to subsequently sort for smaller increments.

public IList ShellSort(IList arrayToSort)
{
    int i, j, increment;
    object temp;

    increment = arrayToSort.Count / 2;

    while (increment > 0)
    {
        for (i = 0; i < arrayToSort.Count; i++)
        {
            j = i;
            temp = arrayToSort[i];
            while ((j >= increment) && (((IComparable)arrayToSort[j - increment]).CompareTo(temp) > 0))
            {
                arrayToSort[j] = arrayToSort[j - increment];
                RedrawItem(j);
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();
                j = j - increment;
            }
            arrayToSort[j] = temp;
            RedrawItem(j);
            pnlSamples.Refresh();
            if (chkCreateAnimation.Checked)
                SavePicture();
        }
        if (increment == 2)
            increment = 1;
        else
            increment = increment * 5 / 11;
    }

    return arrayToSort;
}