Shell Sort

One of the sources of inefficiency in the sorts that we have discussed so far is that the amount of ‘unsortedness’ reduces slowly as items are moved small distances or only limited numbers of items are moved at a time.¬† Shell sort is a well established sort that aims to overcoming these limitations by moving many items large distances at a time.

Conceptually, Shell sort divides the data set into a number of smaller arrays and performs an insertion sort on these smaller arrays. There is some guidance on the initial number of slices to divide the array into, but every data set seems to perform slightly differently. Here we take a conventional approach and divide the set into three initially.

Consider the dataset:

ADS 03 P2 A

We can divide this into three smaller slices:

ADS 03 P2 B

Once we have performed this slicing we can sort each slice:

  • First we sort the first column¬† (16, 9 and 19 ) to give 9, 16, 19
  • Next the second column (4, 10 and 7 ) to give 4, 7, 10
  • Column three (3, 11 and 1 ) to give 1, 3, 11
  • Column four (13, 12 and 2 ) to give 2, 12, 13
  • Column five (5, 17 and 14 ) to give 5, 14, 17
  • Column six (6, 15 and 20 ) to give 6, 15, 20
  • and column seven (8 and 18 ) to give 8, 18

Reassembling the array we now have:

ADS 03 P2 C&D

Notice that elements such as 1 have moved a large distance (from position 17 to position 3).

Next: Shell Sort 2