This algorithm is a simple extension of Insertion sort. Its speed comes from the fact that it exchanges elements that are far apart (the insertion sort exchanges only adjacent elements).

The idea of the Shell sort is to rearrange the file to give it the property that taking every h^th element (starting anywhere) yields a sorted file. Such a file is said to be h-sorted.

SHELL_SORT (A)

for h = 1 to h £ N/9 do
    for (; h > 0; h != 3) do
        for i = h +1 to i £ n do
            v = A[i]
             j = i
            while (j > h AND A[j - h] > v
                    A[i] = A[j - h]
                    j = j - h
            A[j] = v
            i = i + 1

The function form of the running time for all Shell sort depends on the increment sequence and is unknown. For the above algorithm, two conjectures are n(logn)² and n^1.25. Furthermore, the running time is not sensitive to the initial ordering of the given sequence, unlike Insertion sort.

Shell sort is the method of choice for many sorting application because it has acceptable running time even for moderately large files and requires only small amount of code that is easy to get working. Having said that, it is worthwhile to replace Shell sort with a sophisticated sort in given sorting problem.

Implementation

void shellSort(int numbers[], int array_size)
{
  int i, j, increment, temp;

  increment = 3;
  while (increment > 0)
  {
    for (i=0; i < array_size; i++)
    {
      j = i;
      temp = numbers[i];
      while ((j >= increment) && (numbers[j-increment] > temp))
      {
        numbers[j] = numbers[j - increment];
        j = j - increment;
      }
      numbers[j] = temp;
    }
    if (increment/2 != 0)
      increment = increment/2;
    else if (increment == 1)
      increment = 0;
    else
      increment = 1;
  }
}