ShellSort

ShellSort was discovered by a computer scientist named Donald Shell in 1959. It is also referred to as the diminishing 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