# Visual C# 2005 GuideShell Sort

The shell sort was invented by Donald Shell (honestly). It is an improvement on the insertion sort. When you look at each line of output as the insertion sort is executed, you can see that items are exchanged with adjacent items. This means that the larger the distance between an item and its sorted location, the longer it will take to be placed in the right location. The shell sort improves upon this by comparing more distant items. An algorithm for the shell sort is shown below. The variable h represents the distance between the compared items on each pass.

The shell sort is the quickest algorithm of those shown so far, particularly as the number of items increases. There are quicker methods for sorting, but they get more and more complicated to program.

```h = 1 While (h<=arrayLength/3)    h = h * 3 +1 End While While (h > 0)    For outerLoop = h To arrayLength - 1       temp = item[outerLoop]       innerLoop = outerLoop       While (innerLoop > h - 1 And item[innerLoop - h] >= temp)          item[innerLoop] = item[innerLoop - h]          innerLoop = innerLoop - h       End While       item[innerLoop] = temp    Next outerLoop    h = (h - 1)/3 End While```

## Shell Sort Procedure

```static void ShellSort() {    int h = 1;    int inner;    double temp;    while (h <= randomArray.GetLength(0) / 3)    {       h = h * 3 + 1;    }    while (h > 0)    {       for (int outer = h; outer < randomArray.GetLength(0); outer++)       {          temp = randomArray[outer];          inner = outer;          while (inner > h - 1 && randomArray[inner - h] >= temp)          {             randomArray[inner] = randomArray[inner - h];             inner -= h;          }          randomArray[inner] = temp;       }       h = (h - 1) / 3;    } }```

## Having A Go

1. Add this algorithm to your program and compare the execution time of all of the sorting methods covered so far.