Shell sort in Python

Why this matters

Insertion sort is simple, and it is fast on data that is almost sorted. Its weakness is distance. Each step of insertion sort moves a value one position. A small value at the far end of a list must travel all the way to the front, one slot at a time.

Take a list of 1000 values where the smallest value sits at the very end. Insertion sort needs about 999 moves for that one value alone. Every other value that is too far right has the same problem.

Shell sort fixes this by letting values jump. It was published by Donald Shell in 1959. The idea is to run insertion sort on positions that are far apart first. A value can then move many positions in one step. Later passes use smaller distances, and the final pass is a plain insertion sort on a list that is already close to sorted.

The lessons on bubble, selection and insertion sort in this module cover the simple sorts that Shell sort builds on. The nearly sorted insertion sort lesson explains why a nearly sorted list is cheap to finish. This lesson uses both ideas and adds the gap.

The idea: a gap is a distance

A gap is the distance between two positions in the list. With gap 4, position 0 is paired with position 4, position 4 with position 8, and so on. Positions 1, 5, 9 form another chain. Positions 2, 6, 10 form a third chain, and positions 3, 7, 11 form a fourth.

Each chain is a list of values that are gap positions apart. A gapped insertion sort sorts every chain on its own, using ordinary insertion sort on that chain. The values never leave their chain during that pass.

Here is a small example with 8 values:

index:   0   1   2   3   4   5   6   7
value:  23   4  17   9   1  12   6  15

With gap 4 there are four chains of two values:

chain at 0 and 4:  23 and 1      becomes  1 and 23
chain at 1 and 5:   4 and 12     stays    4 and 12
chain at 2 and 6:  17 and 6      becomes  6 and 17
chain at 3 and 7:   9 and 15     stays    9 and 15

After this pass the list is:

index:   0   1   2   3   4   5   6   7
value:   1   4   6   9  23  12  17  15

The value 1 started at index 4 and moved to index 0 in one step. Plain insertion sort would have needed four steps to do the same move.

The next pass uses gap 2. The chains are positions 0, 2, 4, 6 and positions 1, 3, 5, 7.

chain at 0, 2, 4, 6:  1, 6, 23, 17   becomes  1, 6, 17, 23
chain at 1, 3, 5, 7:  4, 9, 12, 15   stays    4, 9, 12, 15

The list is now:

index:   0   1   2   3   4   5   6   7
value:   1   4   6   9  17  12  23  15

The last pass uses gap 1. A gap of 1 makes one chain out of the whole list, so this pass is exactly insertion sort. The list is almost sorted, and the pass finishes quickly. The final list is [1, 4, 6, 9, 12, 15, 17, 23].

Writing it in Python

The program below does the three passes from the example. It has two functions. gapped_insertion runs one pass with a given gap. shell_sort runs a sequence of passes, one for each gap in order.

The output is:

start     [23, 4, 17, 9, 1, 12, 6, 15]
gap 4     [1, 4, 6, 9, 23, 12, 17, 15]
gap 2     [1, 4, 6, 9, 17, 12, 23, 15]
gap 1     [1, 4, 6, 9, 12, 15, 17, 23]
sorted    [1, 2, 3, 5, 6, 7, 8, 9]

The gap pass has the same shape as insertion sort. Read it line by line:

• The outer loop starts at i = gap, not at 1. The first gap values are the first element of each chain, so each one is already in place.
• value holds the item being inserted. j is its current position in the chain.
• The while loop shifts larger chain values one gap to the right until value fits. The check j >= gap stops the loop at the start of the list. It comes first in the test, so Python never reads a position before index 0.
• The line a[j] = value puts the item in its final spot for this pass.

The only change from insertion sort is that every index moves by gap instead of by 1. When gap is 1, the code is exactly insertion sort.

The function shell_sort takes the gaps as separate arguments. The star in *gaps collects every extra argument into a tuple, so the caller decides the sequence. The calls shell_sort(b, 4, 2, 1) and the three separate calls to gapped_insertion do the same work.

Choosing the gap sequence

A gap sequence is the list of gaps used from largest to smallest. Choosing it is the main decision in Shell sort. Every sequence must end with 1. Without the gap 1 pass, the chains never meet, and the result is not sorted. The mistakes section below shows this.

The sequence does not affect correctness, as long as it ends with 1. It affects how many moves the sort makes. The sequences below are four common choices. The gap lists for an array of 20 values are:

Shell's original (halve the length):  10, 5, 2, 1
Hibbard (2^k - 1):                     15, 7, 3, 1
Knuth (3h + 1, up to length / 3):       4, 1
Ciura (table of values):               10, 4, 1

Here is what each rule means.

Shell's original starts at half the length and halves the gap each time, using whole-number division. It is the simplest rule and the one from the 1959 paper. Its weakness is that some inputs are still slow, because the gaps share common factors, such as 10 and 5. Passes with such gaps can keep values in the same groups, so some inputs need about n times n steps.

Hibbard's sequence uses numbers one less than a power of 2: 1, 3, 7, 15, 31 and so on. Two neighbouring gaps in this list have no common factor other than 1. The worst case improves to about n^1.5, which means n times the square root of n.

Knuth's sequence starts at 1, then uses 4, 13, 40 and so on, where each value is 3 times the last plus 1. The program builds the list from the small end and stops at the largest value that is no more than the length divided by 3. For 20 values the largest value is 4 because 13 is more than 20 divided by 3, which is 6.

Ciura's sequence is a fixed table of 1, 4, 10, 23, 57, 132, 301 and 701. Its values were found by experiment on random lists, not by a formula or a proof. For a list longer than 701, the usual extension is to keep multiplying the largest value by about 2.25. Use it when measured speed matters more than a clean rule.

The program below counts the moves each sequence makes. A move is one value shifted one gap to the right. The global moves lines let the functions change that counter, which is defined outside them. The test uses 1000 values and a fixed random seed, so the numbers repeat on every run. The gap lists are written from largest to smallest, as the passes run.

The output is:

random input, n=1000
shell      gaps=[500, 250, 125, 62, 31, 15, 7, 3, 1] moves=7711 sorted=True
hibbard    gaps=[511, 255, 127, 63, 31, 15, 7, 3, 1] moves=6879 sorted=True
knuth      gaps=[121, 40, 13, 4, 1] moves=9938 sorted=True
ciura      gaps=[701, 301, 132, 57, 23, 10, 4, 1] moves=6797 sorted=True
insertion  gaps=[1] moves=237493 sorted=True
reversed input, n=1000
shell      gaps=[500, 250, 125, 62, 31, 15, 7, 3, 1] moves=4700 sorted=True
hibbard    gaps=[511, 255, 127, 63, 31, 15, 7, 3, 1] moves=3424 sorted=True
knuth      gaps=[121, 40, 13, 4, 1] moves=5990 sorted=True
ciura      gaps=[701, 301, 132, 57, 23, 10, 4, 1] moves=3090 sorted=True
insertion  gaps=[1] moves=499500 sorted=True
gap lists for n=20
shell   [10, 5, 2, 1]
hibbard [15, 7, 3, 1]
knuth   [4, 1]
ciura   [10, 4, 1]

Read the numbers with care. The random input gives very different totals from the reversed input. Insertion sort, which is the gap 1 case alone, needs about 237000 moves on random data and about 500000 on reversed data. Every gap sequence in the table cuts that by a large factor. The best sequence here, Ciura's, uses about 6800 moves on random data. Knuth's sequence uses more moves than Shell's original on this input, even though its worst case is better. These numbers come from one size and one seed. They show the pattern, not a ranking that holds for every input.

The gap lists are written from the largest gap to the smallest, because the passes must run in that order. The function shell_gaps uses append, which adds each smaller gap at the end. The functions for Hibbard and Knuth use insert(0, ...), which puts each new value at the front. The Ciura function reverses its table with reversed. Each way gives a list that runs from large to small.

Mistakes

Testing the index after the value

The most common bug is putting the check j >= gap in the wrong place in the while test. Python checks the conditions from left to right and stops at the first false one. In the correct order, the check on j comes first, so a[j - gap] is never read when j is too small. In the wrong order, Python reads a[j - gap] first, and when j - gap is negative, it reads from the end of the list.

This version has the two conditions in the wrong order:

The output is:

wrong test order, gap 4: [1, 4, 6, 9, 23, 12, 17, 15]

The list is right, and no error appeared. That is the danger. The loop still stops in time, because the body of the loop does not run when j is too small, so the read of a negative position changes nothing here. The read is still a mistake. It reads a value that the algorithm should never touch, and the code only works by luck of the order of the steps. The fix is the order in this lesson, with j >= gap first. In Java this same bug stops the program with an ArrayIndexOutOfBoundsException, so the Java error is easier to see, and Python needs careful reading.

Forgetting the gap 1 pass

If the gap list stops before 1, the list is only partly sorted. Each chain is sorted, but the chains are not merged. The code runs without an error and prints a wrong answer.

This program runs gaps 4 and 2 only:

The output is:

[1, 4, 6, 9, 17, 12, 23, 15]

The values 17 and 12 are out of order, and 23 comes before 15. The fix is to run the gap 1 pass as the last pass, so the gap list ends with 1. In the code of this lesson, that means the loop for gap in [4, 2, 1].

A loop that never ends

When a gap list is built by halving, the loop test must stop when the gap reaches 0. A test that allows 0 never stops, because 0 divided by 2 is still 0. The loop below has that problem:

gap = n // 2
while gap >= 0:
    gapped_insertion(a, gap)
    gap //= 2

With this loop the program does not finish. A gap of 0 makes the pass do nothing, and the loop keeps asking for the next gap, which is 0 again. The fix is the test gap > 0. Any loop that divides a gap must have a test that rejects 0. Do not run this loop to see it stop, because it will not.

Mixing up gap and chain length

A gap of 4 in a 20-value list gives five values per chain, not four. The number of chains equals the gap, and the length of each chain is about the list length divided by the gap. Learners often count the chain length as the gap. Writing the chains out for a short list, as this lesson does, catches the mistake.

Using a sequence that is not in decreasing order

The loop runs the gaps in the order given. If the list goes 1, 4, 13, the first pass is a plain insertion sort, and it does all the moving. The later passes find the list already sorted and move nothing. The result is still sorted, and the total work is the same as plain insertion sort. Keep the list in decreasing order, as every sequence in this lesson is.

Practice

Practice 1. Trace one gapped pass by hand. Use gap 4 on [8, 3, 9, 1, 7, 2, 6, 5]. Write the four chains and the list after the pass.

Show the answer

The chains are (8, 7) at positions 0 and 4, (3, 2) at 1 and 5, (9, 6) at 2 and 6, and (1, 5) at 3 and 7. Sorted, they become (7, 8), (2, 3), (6, 9) and (1, 5). The list is [7, 2, 6, 1, 8, 3, 9, 5]. Running the code confirms the result.

Practice 2. Write the gap list for Shell's original rule with a list of length 100. Use whole-number division.

Show the answer

The gaps are 50, 25, 12, 6, 3 and 1. Each value is the previous one divided by 2, with the fraction dropped. The list ends at 1 because 1 divided by 2 is 0, which stops the loop. The program shell_gaps(100) in this lesson prints the same list.

Practice 3. Using the rule in this lesson, find the Knuth gap list and the Hibbard gap list for a list of length 50. Explain why Knuth stops where it does.

Show the answer

Knuth's list is 13, 4, 1, because 1, 4 and 13 are all at most 50 divided by 3, which is 16. The next value, 40, is more than 16, so it is left out. Hibbard's list is 31, 15, 7, 3, 1, because each value is one less than a power of 2 and no more than 50. The next power, 63, is too large.

Practice 4. Insertion sort (gap 1) and gap 2 both sort [9, 7, 5, 3, 1]. Predict which one makes more moves, then count them by hand. A move is one value shifted one gap to the right.

Show the answer

Gap 1 makes 10 moves. Each value shifts past every larger value before it, so the counts are 1, 2, 3 and 4. Gap 2 makes 4 moves. Its chains are (9, 5, 1) and (7, 3). After that pass the list is [1, 3, 5, 7, 9]. The moves were 1 for value 5, 1 for value 3 and 2 for value 1. Gap 2 needs fewer moves because the value 1 jumps two positions at a time, so it passes the larger values in fewer steps.

Practice 5. The loop below has a bug. Find it, explain what goes wrong, and write the fixed loop.

gap = n // 2
while gap > 1:
    gapped_insertion(a, gap)
    gap //= 2

Show the answer

The test gap > 1 stops before gap 1. The gap 1 pass is the one that makes the list fully sorted, so the result can be out of order without any error message. The fixed loop is while gap > 0:.

Summary

• Shell sort runs insertion sort on chains of positions that are gap apart, starting with a large gap.
• Each pass lets values move far in one step, so the last pass (gap 1) has little left to fix.
• The gap sequence decides the total work. Shell's original, Hibbard, Knuth and Ciura lists give different counts.
• Every gap sequence must end with 1, and the loop must stop only after the gap 1 pass runs.
• Put the index check first in the while test, so Python never reads a position before the start of the list.
• Shell sort needs no extra list. It rearranges the values in place, like the other sorts in this module.