The SHELL sort.

  The shell sort is the hardest of the the three basic sorting routines to understand. Don't worry if you have problems trying to make sense of it, just take your time.
  The shell sort consists of a series of bubble sorts, performed on bigger and bigger groups of numbers. To start, the entire list in divided into two halves, and the first item in each half are compared and sorted. On the next pass of the routine, the entire list is divided into four quaters, and the first item of every quarter is sorted using a bubble sort. Then the list is divided into eighths, and the first item of every eighth bubble sorted. And so on until, on the final pass the entire list is bubble sorted.
  The file B.SHELL on the disk is, unsurprisingly a shell sort program. Like the previous two example programs, the state of the partially sorted data is shown after each pass of the shell sort routine. The state of the data is not however shown during the 'sub' bubble sorts.