Shell sort in C#

Shell sort - overview

Shell sort is a sorting algorithm developed by Donald Shell in 1959. It is an in-place comparison sort.

Shell noticed that the two other sorting algorithms bubble sort and insertion sort only moved elements one location at a time. It means that each element must move quite far before it finds its correct location. With Shells algorithm it is possible for elements to jump several locations at a time, which improves the execution time.

Shell sort can be viewed as a generalized version of insertion sort.

Description of the Shell sort algorithm

Shell sort works in the same way as insertion sort, but with the difference that the outer loop in insertion sort is surrounded with another loop. This extra loop is called the gap loop.

Instead of sorting values one by one, as in the insertion sort algorithm, we can now perform an insertion sort every g values (where g is equal to the gap value).

After each round of sorting g should be decreased. Shell suggested the following gap sequence:

N/2, N/4, ... , 1

The last round always has a gap size of 1, and that corresponds to a round with the original insertion sort. The previous sorting rounds makes the array almost sorted so that the array is prepared for the final round, so that it does not have to move the elements very far. Insertion sort is namely very quick if the elements in the array are already "roughly" sorted.

Any diminishing sequence can be used as gap sequence as long as the last value is 1. However, the computational complexity is quite dependent on the gap sequence. For example, instead of dividing the value by 2, the value 2.2 could be used. It has been shown that that value gives better performance than 2.

Computational complexity

Worst case performance is O(n²). Best case performance O(n log n). Average case performance depends on selection of gap sequence.

Example of an implementation of Shell sort in C#

    private void SortArrayWithShellSort()
    {
        int[] array = { 7, 5, 17 };
        ShellSort(array);

        // PrintResult(array);
    }
        
    private void ShellSort(int[] array)
    {
        int n = array.Length;
        int gap = n / 2;
        int temp;

        while (gap > 0)
        {
            for (int i = 0; i + gap < n; i++)
            {
                int j = i + gap;
                temp = array[j];

                while (j - gap >= 0 && temp < array[j - gap])
                {
                    array[j] = array[j - gap];
                    j = j - gap;
                }

                array[j] = temp;
            }

            gap = gap / 2;
        }
    }