The Shell Sort Algorithm

The shell sort quickly arranges data by sorting every n-{th} element, where n can be any number less than half the number of data. Once the initial sort is performed, n is reduced, and the data is sorted again, with this process repeating until until n equals 1. It is vital that the data is finally sorted with n=1, otherwise there may be out-of-order elements remaining.

Selecting good values for n

Choosing n is not as difficult as it might seem. The only sequence you have to avoid is one constructed with the powers of 2. Do not choose (for example) 16 as your first n, and then keep dividing by 2 until you reach 1. It has been mathematically proven that using only numbers from the power series {1, 2, 4, 8, 16, 32, ...} produces the worst sorting times. The fastest times are (on average) obtained by choosing an initial n somewhere close to the maximum allowed and continually dividing by 2.2 until you reach 1 or less. Remember to always sort the data with n=1 as the last step.

Example:

The data in the table needs to be sorted into ascending order. For simplicity, we have chosenrespectively. Elements in the table that have a white background are being ignored in that step. Elements with a yellow background are the ones we are interested in. The top line of each table shows the data before we performed that step, the bottom shows the data afterwards.

In this example, we will assume there is a selection sort being used to do the actual sorting.

As mentioned above, we will be using an initial value of 3 for n. This is less than the maximum (which in this case is 4, because this is the largest number less than half the number of elements we have).

We pretend that the only elements in the data set are elements containing 5, 8 and 9 (highlighted blue). Notice that this is every 3rd element (n is 3). After sorting these, we look at the elements to the right of the ones we just looked at. Repeat the sort and shift routine until all of the elements have been looked at once. So ifyou will need to repeat this step 3 times to sort every element. Note that only the highlighted elements are ever changed; the ones with a white background are totally ignored.

Put the 8, 5 and 9 into ascending order (ignoring the other elements)

Do the same for 4, 7 and 3

As well as 1, 6 and 2...

Now that all of the elements have been sorted once withwe repeat the process with the next value of n (2).

Place the odd elements into ascending order

And the same for the even elements...

All that remains is to sort it again withto fix up any elements that are still out of order.

The few elements which are still out of order are fixed.