ShellSortwas discovered by a computer scientist named Donald Shell in 1959. It is also referred to as thediminishing gap sort.It is based on

`InsertionSort`

, but adds a new feature that improves performance. The basic idea behind this sort is that in early stages, far-apart elements are compared, rather than adjacent ones as in simplier exchange sorts. This tends to eliminate large amounts of disorder quickly, so later stages have less work to do. The interval (i.e. gap) between compared elements is gradually decreased to one, at which point the sort effectively becomes an exchange method. The performance of this algorithm can be influenced by the gaps that are used.

`ShellSort`

is good for medium-sized arrays (few thousand items). By default,`ShellSort`

should probably be your choice for sorting. If performance becomes an issue, then change to a more advanced sorting technique such as`QuickSort`

.

`ShellSort`

pseudo-code:// assume we have an array 'a' with length 'n' for (gap = n/2; gap > 0; gap /= 2) { for (i = gap; i < n; i++) for (j = i-gap; j >= 0; j -= gap) { if (!COMPARE (a, j, j+gap)) break; SWAP (a, j, j+gap); } }YouTube.com::Java Shell Sort by Derek Banas