Shell Sort

procedure shell(var a : anarray; N : integer);

 var i, j, h, v : integer;

begin

  h := 1;
  repeat
   h := 3*h + 1
  until h > N;

  repeat
   h := h div 3;
   for i := h+1 to N do
    begin
     v := a[i]
     j := i;
     while (j > h) AND (a[j-h] > v) do
      begin
        a[j] := a[j-h]
        j := j - h;
      end;
     avj] := v;
    end
   until h = 1;

end;

Back to Sorting Algorithms

Shell Sort was invented by David Shell. It's one of the fastest true in-place sorting algorithms (the fastest is Heap Sort) and the fastest of the polynomial time algorithms, clocking at O(n^(1.5)).

Shell started with the insertion sort, which is about twice as fast as bubble sort, and introduced gaps between compared cells. Shell originally used the sequence (..., 8, 4, 2, 1) for gap sizes, but Knuth has demonstrated that the sequence (..., 40, 13, 4, 1), where gap_{i - 1} = 3*gap_i + 1, gets the job done more quickly.

/* shell sort */

typedef int T; /* replace int with the type to be sorted */
#define compGT(a,b) (a > b)

void shellSort(T *a, tblIndex lb, tblIndex ub)
{
  size_t n, h, i, j; /* table indices */
  T t; /* current comparison key */

  /* sort array indices a[lb..ub] inclusive
   * this might be useful for small (< 10 elements)
   * sub-arrays in recursive algorithms such as merge sort
   * or quick sort
   */

  /* compute largest increment */
  n = ub - lb + 1;
  h = 1;
  if (n < 14)
    h = 1;
  else if (sizeof(tblIndex) == 2 && n > 29524)
    h = 3280;
  else
  {
    while (h < n)
      h = 3*h + 1;
    h /= 3;
  }

  while (h > 1)
  {
    /* compute next increment */
    h /= 3;

    /* insertion sort in increments of h */
    for (i = lb + h; i <= ub; i++)
    {
      t = a[i];
      for (j = i-h; j >= lb && compGT(a[j], t); j -= h)
        a[j+h] = a[j];
      a[j+h] = t;
    }
  }
}