7.5. Shellsort¶

Shellsort was named for its inventor, D.L. Shell, who published it in 1959. When properly implemented, Shellsort will give much better performance than any of the \(O(n^{2})\) sorts like insertion sort or selection sort. But it is also a bit more complicated than those simple \(O(n^{2})\) sorts. Unlike insertion sort and selection sort, there is no real-life intuition to inspire Shellsort -- nobody will use Shellsort to sort their Bridge hand or organize their bills.

The key idea behind Shellsort is to exploit the best-case performance of insertion sort. Recall that when a list is sorted or nearly sorted, insertion sort runs in linear time. So Shellsort’s strategy is to quickly make the list "mostly sorted", so that a final insertion sort can finish the job.

Shellsort does what most good sorts do: Break the input into pieces, sort the pieces, then recombine them. But Shellsort does this in an unusual way, breaking its input into "virtual" sublists that are often not contiguous.

Shellsort uses an increment, sometimes called the gap, to create a sublist by choosing all items that are gap items apart. Each such sublist is sorted using an insertion sort. Another group of sublists is then chosen and sorted, and so on.

The following sequence uses a vector with nine items and a gap of three. This creates three sublists, each sorted using insertion sort. The last scene shows the values in their positions after one pass through all three sublists.

Shellsort: one pass with a gap of three

Scene 1: Gap 3: sort sublist 1 at positions 0, 3, and 6.

A gap of three creates three sublists. Their positions are fixed; values move only between positions in the same sublist during this pass. The outlined cells contain sublist 1: [54, 17, 44].

Use insertion sort within this sublist. Insert 17 before 54, then insert 44 between 17 and 54. Its sorted values are [17, 44, 54].

Before the gap-three pass, sublist 1 occupies positions 0, 3,
and 6.

Text description

Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “93”, index 3: “17”, index 4: “77”, index 5: “31”, index 6: “44”, index 7: “55”, and index 8: “20”.

index 0: “54”, index 3: “17”, and index 6: “44” are highlighted.

Sublists before the gap-three pass¶
Sublist	Zero-based positions	Original values in position order
1	0, 3, 6	54, 17, 44
2	1, 4, 7	26, 77, 55
3	2, 5, 8	93, 31, 20

Scene 2: Sublist 1 is sorted in positions 0, 3, and 6.

The values [17, 44, 54] now occupy positions 0, 3, and 6, respectively. Positions belonging to sublists 2 and 3 are unchanged. Only sublist 1 has been sorted so far.

After sorting sublist 1, positions 0, 3, and 6 contain 17, 44,
and 54.

Text description

Array with 9 cells. From left to right: index 0: “17”, index 1: “26”, index 2: “93”, index 3: “44”, index 4: “77”, index 5: “31”, index 6: “54”, index 7: “55”, and index 8: “20”.

index 0: “17”, index 3: “44”, and index 6: “54” are highlighted.

Scene 3: Sort sublist 2 at positions 1, 4, and 7.

The outlined cells contain sublist 2: [26, 77, 55]. Its positions are one cell to the right of those in sublist 1.

Use insertion sort within this sublist. Leave 77 after 26, then insert 55 between them. Its sorted values are [26, 55, 77].

Sublist 2 contains 26, 77, and 55 at positions 1, 4, and 7.

Text description

index 1: “26”, index 4: “77”, and index 7: “55” are highlighted.

Scene 4: Sublist 2 is sorted in positions 1, 4, and 7.

The values [26, 55, 77] now occupy positions 1, 4, and 7, respectively. Sublist 1 retains its sorted values, and sublist 3 has not yet been processed.

After sorting sublist 2, positions 1, 4, and 7 contain 26, 55,
and 77.

Text description

Array with 9 cells. From left to right: index 0: “17”, index 1: “26”, index 2: “93”, index 3: “44”, index 4: “55”, index 5: “31”, index 6: “54”, index 7: “77”, and index 8: “20”.

index 1: “26”, index 4: “55”, and index 7: “77” are highlighted.

Scene 5: Sort sublist 3 at positions 2, 5, and 8.

The outlined cells contain sublist 3: [93, 31, 20]. Its positions are two cells to the right of those in sublist 1.

Use insertion sort within this sublist. Insert 31 before 93, then insert 20 before both of them. Its sorted values are [20, 31, 93].

Sublist 3 contains 93, 31, and 20 at positions 2, 5, and 8.

Text description

index 2: “93”, index 5: “31”, and index 8: “20” are highlighted.

Scene 6: Sublist 3 is sorted in positions 2, 5, and 8.

The values [20, 31, 93] now occupy positions 2, 5, and 8, respectively. Sublists 1 and 2 retain their sorted values. The pass through all three sublists is complete.

After sorting sublist 3, positions 2, 5, and 8 contain 20, 31,
and 93.

Text description

Array with 9 cells. From left to right: index 0: “17”, index 1: “26”, index 2: “20”, index 3: “44”, index 4: “55”, index 5: “31”, index 6: “54”, index 7: “77”, and index 8: “93”.

index 2: “20”, index 5: “31”, and index 8: “93” are highlighted.

Scene 7: The gap-three pass is complete.

All three sublists are sorted within their original positions. Reading across the array gives [17, 26, 20, 44, 55, 31, 54, 77, 93].

The whole array is still not sorted: 26 precedes 20, and 55 precedes 31. Sorting the sublists has moved values closer to their final positions. A later pass with a gap of one will finish the sort.

After the gap-three pass: 17, 26, 20, 44, 55, 31, 54, 77, 93.

Text description

Sorted sublists after the gap-three pass¶
Sublist	Zero-based positions	Sorted values in position order
1	0, 3, 6	17, 44, 54
2	1, 4, 7	26, 55, 77
3	2, 5, 8	20, 31, 93

The gap-one sequence shows the final pass of the previous example: a standard insertion sort. Sorting the gap-three sublists first reduces the shifting needed to put the whole array in order. This final pass requires only four shifts.

Shellsort: the final pass with a gap of one

Scene 1: Gap 1: start with the array from the gap-three pass.

A gap of one makes the whole array a single sublist. Finish with a standard insertion sort, starting with 17 as the sorted prefix. The outlined cells mark that prefix as it grows.

Gap-one pass: the first 1 cells form the sorted prefix.

Text description

index 0: “17” is highlighted.

Scene 2: Insert 26: no shifts.

Since 26 is greater than 17, leave it in place. The sorted prefix now contains two items.

Gap-one pass: the first 2 cells form the sorted prefix.

Text description

index 0: “17” and index 1: “26” are highlighted.

Scene 3: Insert 20: shift 26 once.

Save 20, shift 26 one cell to the right, and insert 20 after 17. The sorted prefix now contains three items. This is the first of four shifts needed to finish the sort.

Gap-one pass: the first 3 cells form the sorted prefix.

Text description

Array with 9 cells. From left to right: index 0: “17”, index 1: “20”, index 2: “26”, index 3: “44”, index 4: “55”, index 5: “31”, index 6: “54”, index 7: “77”, and index 8: “93”.

index 0: “17”, index 1: “20”, and index 2: “26” are highlighted.

Scene 4: Insert 44: no shifts.

Since 44 is greater than 26, leave it in place. The sorted prefix now contains four items.

Gap-one pass: the first 4 cells form the sorted prefix.

Text description

index 0: “17”, index 1: “20”, index 2: “26”, and index 3: “44” are highlighted.

Scene 5: Insert 55: no shifts.

Since 55 is greater than 44, leave it in place. The sorted prefix now contains five items.

Gap-one pass: the first 5 cells form the sorted prefix.

Text description

index 0: “17”, index 1: “20”, index 2: “26”, index 3: “44”, and index 4: “55” are highlighted.

Scene 6: Insert 31: shift 55 and 44.

Save 31, shift 55 and 44 one cell to the right, then insert 31 after 26. The sorted prefix now contains six items. These two shifts bring the total to three.

Gap-one pass: the first 6 cells form the sorted prefix.

Text description

Array with 9 cells. From left to right: index 0: “17”, index 1: “20”, index 2: “26”, index 3: “31”, index 4: “44”, index 5: “55”, index 6: “54”, index 7: “77”, and index 8: “93”.

index 0: “17”, index 1: “20”, index 2: “26”, index 3: “31”, index 4: “44”, and index 5: “55” are highlighted.

Scene 7: Insert 54: shift 55 once.

Save 54, shift 55 one cell to the right, and insert 54 after 44. The sorted prefix now contains seven items. This fourth shift is the last one needed.

Gap-one pass: the first 7 cells form the sorted prefix.

Text description

Array with 9 cells. From left to right: index 0: “17”, index 1: “20”, index 2: “26”, index 3: “31”, index 4: “44”, index 5: “54”, index 6: “55”, index 7: “77”, and index 8: “93”.

index 0: “17”, index 1: “20”, index 2: “26”, index 3: “31”, index 4: “44”, index 5: “54”, and index 6: “55” are highlighted.

Scene 8: Insert 77: no shifts.

Since 77 is greater than 55, leave it in place. The sorted prefix now contains eight items.

Gap-one pass: the first 8 cells form the sorted prefix.

Text description

index 0: “17”, index 1: “20”, index 2: “26”, index 3: “31”, index 4: “44”, index 5: “54”, index 6: “55”, and index 7: “77” are highlighted.

Scene 9: Insert 93: the array is sorted.

Since 93 is greater than 77, leave it in place. All nine items now belong to the sorted prefix. The gap-one pass needed only four shifts: one for 20, two for 31, and one for 54.

Gap-one pass: the first 9 cells form the sorted prefix.

Text description

index 0: “17”, index 1: “20”, index 2: “26”, index 3: “31”, index 4: “44”, index 5: “54”, index 6: “55”, index 7: “77”, and index 8: “93” are highlighted.

Shellsort: initial sublists with a gap of four

Scene 1: Gap 4: sublist 1 occupies positions 0, 4, and 8.

This separate example returns to the original, unsorted array. The implementation below starts with a gap of \(9 / 2\), using integer division to get four. Later gaps are two and one.

The outlined cells form sublist 1: [54, 77, 20]. They are four positions apart. Insertion sort will sort these values within positions 0, 4, and 8.

Gap-four sublist 1 occupies positions 0, 4, 8.

Text description

index 0: “54”, index 4: “77”, and index 8: “20” are highlighted.

Scene 2: Sublist 2 occupies positions 1 and 5.

The outlined cells form sublist 2: [26, 31]. This sublist starts at position 1 and advances by four positions. Its values are already in ascending order.

Gap-four sublist 2 occupies positions 1, 5.

Text description

index 1: “26” and index 5: “31” are highlighted.

Scene 3: Sublist 3 occupies positions 2 and 6.

The outlined cells form sublist 3: [93, 44]. This sublist starts at position 2 and advances by four positions. Sorting it will place 44 at position 2 and 93 at position 6.

Gap-four sublist 3 occupies positions 2, 6.

Text description

index 2: “93” and index 6: “44” are highlighted.

Scene 4: Sublist 4 occupies positions 3 and 7.

The outlined cells form sublist 4: [17, 55]. This sublist starts at position 3 and advances by four positions. Its values are already in ascending order.

These four sublists cover every position in the original array. The table summarizes their positions and values before sorting.

Gap-four sublist 4 occupies positions 3, 7.

Text description

index 3: “17” and index 7: “55” are highlighted.

Initial sublists with a gap of four¶
Sublist	Zero-based positions	Original values in position order
1	0, 4, 8	54, 77, 20
2	1, 5	26, 31
3	2, 6	93, 44
4	3, 7	17, 55

Shell Sort

We said earlier that the way in which the increments are chosen is the unique feature of the Shellsort. The function shown in the Run It section. uses a different set of increments. In this case, we begin with \(\frac {n}{2}\) sublists. On the next pass, \(\frac {n}{4}\) sublists are sorted. Eventually, a single vector is sorted with the basic insertion sort. The gap-four scenes show the first sublists for our example using this increment.

The following invocation of the shell_sort function shows the partially sorted vectors after each increment, with the final sort being an insertion sort with an increment of one.

Run It

The Shell Sort

 1#include <iostream>
 2#include <string>
 3#include <vector>
 4using std::vector;
 5
 6void print(const vector<int>& data, const std::string& comment) {
 7   for (const auto& value: data) {
 8      std::cout << value << ' ';
 9   }
10   std::cout << comment << '\n';
11}
12
13vector<int> gap_insertion_sort(vector<int> data, int start, int gap) {
14   for (int i = start+gap; i < int(data.size()); i += gap) {
15      int value = data[i];
16      int pos = i;
17
18      while (pos >= gap && data[pos-gap] > value) {
19         data[pos] = data[pos-gap];
20         pos -= gap;
21      }
22      data[pos] = value;
23   }
24   return data;
25}
26
27vector<int> shell_sort(vector<int> data) {
28   int pivot = data.size() / 2;
29   while (pivot > 0) {
30      for (int start = 0; start < pivot; ++start) {
31         data = gap_insertion_sort(data, start, pivot);
32      }
33      std::string text = ": pivot = ";
34      text.append(std::to_string(pivot));
35      print(data, text);
36      pivot /= 2;
37   }
38   return data;
39}
40
41int main() {
42  vector<int> data = {54, 26, 93, 17, 77, 31, 44, 55, 20};
43  print(shell_sort(data), ": done");
44  return 0;
45}

The following animations show the Shellsort in action. Teal marks the current gap group, yellow marks the value being inserted, red marks a shifted comparison, and gray marks the final sorted state.

Average case

Best case

Worst case

7.5.1. Shellsort analysis¶

At first glance you may think that a Shellsort cannot be better than an insertion sort, since it does a complete insertion sort as the last step. It turns out, however, that this final insertion sort does not need to do very many comparisons (or shifts) since the list has been pre-sorted by earlier incremental insertion sorts, as described above. In other words, each pass produces a list that is "more sorted" than the previous one. This makes the final pass very efficient.

Although a general analysis of the Shellsort is well beyond the scope of this text, we can say that it tends to fall somewhere between \(O(n)\) and \(O(n^{2})\), based on the behavior described above. For the increments shown in the Run It section the performance is \(O(n^{2})\).

Some choices for the series of increments will make Shellsort run more efficiently than others. In particular, the choice of increments described above \((\frac{N}{2^{k}},\ldots,4,2,1)\) turns out to be relatively inefficient. Notice for example that all records in a given 8 increment sublist are also part of some 4 increment sublist, which are all in turn records of the same 2 increment sublist. So there is no "crossover" between sublists as the increments reduce. By changing the increment, for example using \((2^{k}-1,\ldots,31,15,7,3,1)\) a shell sort can perform at \(O(n^{\frac {3}{2}})\).

Shellsort is not so much worse than the asymptotically better sorts to be presented later, whenever \(n\) is of medium size (though it tends to be a little slower than these other algorithms if they are well implemented). Shellsort illustrates how we can sometimes exploit the special properties of an algorithm (like insertion sort) even if in general that algorithm is unacceptably slow.

Self Check

Given the following list of numbers: [5, 16, 20, 12, 3, 8, 9, 17, 19, 7], which answer illustrates the contents of the list after all swapping is complete for a gap size of 3?

[5, 3, 8, 7, 16, 19, 9, 17, 20, 12]

Each group of numbers represented by index positions 3 apart are sorted correctly.

[3, 7, 5, 8, 9, 12, 19, 16, 20, 17]

This solution is for a gap size of two.

[3, 5, 7, 8, 9, 12, 16, 17, 19, 20]

This is list completely sorted, you have gone too far.

[5, 16, 20, 3, 8, 12, 9, 17, 20, 7]

The gap size of three indicates that the group represented by every third number e.g. 0, 3, 6, 9 and 1, 4, 7 and 2, 5, 8 are sorted not groups of 3.

More to Explore