Shellsort
This page gives a brief introduction to Shellsort.
Definition
Shellsort, also known as diminishing increment sort, is an improved version of insertion sort. It is named after its inventor, Donald Shell.
Procedure
Shellsort compares and moves records that are not adjacent:
- Split the sequence to be sorted into several subsequences (the elements of each subsequence are the same distance apart in the original array);
- Sort these subsequences by insertion sort;
- Reduce the gap between the elements of each subsequence, and repeat the steps above until the gap is down to \(1\).
To make the analysis easier, here is pseudocode for a single insertion sort with gap \(h\), denoted \(\text{InsertionSort}(h)\). The array \(A\) is indexed from \(1\) to \(n\), and \(v\) holds the value currently being inserted; Shellsort calls this procedure with the gaps in decreasing order.
Properties
Stability
Shellsort is an unstable sorting algorithm.
Time complexity
The best-case running time of Shellsort depends on the gap sequence and on whether the implementation exits early; the \(3h+1\) implementation given below, which does not exit early, takes \(\Theta(n\log n)\) in the best case.
The average-case time complexity and the worst-case time complexity of Shellsort depend on the choice of gap sequence. Let the gap sequence be \(H\). Here are two classic choices of \(H\), both of which bring the complexity of the sort down to \(o(n^2)\).
Proposition 1
If the gap sequence is \(H= \{ 2^k-1\mid k=1,2,\ldots,\lfloor\log_2 n\rfloor \}\) (in decreasing order), Shellsort runs in \(O(n^{3/2})\).
Proposition 2
If the gap sequence is \(H= \{ k=2^p\cdot 3^q\mid p,q\in \mathbb N,k\le n \}\) (in decreasing order), Shellsort runs in \(O(n\log^2 n)\).
To prove these two propositions, we first state and prove an important theorem, which captures the most essential feature of Shellsort.
Theorem 1
Once the program has executed \(\text{InsertionSort}(h)\), each of the following subsequences stays sorted, no matter how the \(\text{InsertionSort}\) function is called afterwards and how the array \(A\) changes:
We now prove Theorem 1.
We begin by proving Lemma 1.
Lemma 1
Let \(n\) and \(m\) be non-negative integers, \(l\) a positive integer, and \(X(x_1,x_2,\ldots,x_{n+l})\) and \(Y(y_1,y_2,\ldots,y_{m+l})\) two arrays that satisfy the following condition:
Then the condition still holds after each of the two arrays is sorted in ascending order.
Proof of Lemma 1
Let \(X'(x'_1,\ldots,x'_{n+l})\) be the array \(X\) after sorting, and \(Y'(y'_1,\ldots,y'_{m+l})\) the array \(Y\) after sorting.
For any \(1\le i\le l\), at most \(l-i\) elements of \(X\) are strictly greater than \(x'_{n+i}\). So among the \(l\) selected elements \(\{x_{n+1},\ldots,x_{n+l}\}\), at least \(i\) are no greater than \(x'_{n+i}\). Call them \(x_{n+k_1},\ldots,x_{n+k_i}\). Together with the original pairwise inequalities, this gives:
So \(x'_{n+i}\) is greater than or equal to at least \(i\) elements of \(Y\), which are also the elements of \(Y'\), and therefore \(y'_i\le x'_{n+i}\,(1\le i\le l)\).
Back to the proof of the original statement. Let \(N\) be the length of the array. It suffices to show that \(\text{InsertionSort}(k)\) keeps an \(h\)-sorted array \(h\)-sorted; the theorem then follows by induction on the number of calls. Here \(h\) and \(k\) are arbitrary positive integers. If \(h\ge N\), there are no pairs of elements at distance \(h\) to check, and the claim holds trivially. From now on, assume \(h<N\).
Let \(A\) and \(A'\) be the array before and after the call. Before the call, \(A_i\le A_{i+h}\) for \(1\le i\le N-h\). For each \(1\le w\le\min(k,N-h)\), use division with remainder to write
Consider the two complete subsequences with gap \(k\) that start at indices \(w\) and \(v\):
Let \(l\) be the number of non-negative integers \(j\) with \(w+h+jk\le N\). Then \(X\) has length \(t+l\), and \(Y\) has length at least \(l\). Since the array was \(h\)-sorted, the first \(l\) terms of \(Y\) and the last \(l\) terms of \(X\) satisfy
What \(\text{InsertionSort}(k)\) does is precisely to sort each of these complete subsequences in ascending order. By Lemma 1, the correspondence still holds after sorting, that is,
The lemma applies even when \(v=w\) and the two subsequences are in fact the same. Every index \(1\le i\le N-h\) can be written uniquely as \(i=w+jk\) with \(1\le w\le k\) and \(j\ge0\), and then necessarily \(w\le N-h\). So the argument above covers every \(i\) and gives \(A'_i\le A'_{i+h}\): the array remains \(h\)-sorted, which proves Theorem 1.
This theorem is the key to why Shellsort achieves a better complexity for particular sets \(H\): throughout the process, the subsequences sorted so far all stay sorted, so in later calls the pointer \(i\) moves far fewer times.
Next we single out a lemma from number theory and prove it. It became very famous in the OI community through the problem Xiaokai's Puzzle. In the proof of the complexity of Shellsort, it also extends Theorem \(1\) considerably.
Lemma 2
If \(a,b\ge2\) are coprime integers, then the largest positive integer not in the set \(\{ax+by\mid x,y\in \mathbb N \}\) is \(ab-a-b\).
Proof of Lemma 2
The proof has two steps:
-
First we show that the equation \(ax+by=ab-a-b\) has no solution in which \(x\) and \(y\) are both non-negative integers:
Without the restriction to non-negative integers, two solutions are easy to find: \((b-1,-1)\) and \((-1,a-1)\).
The general solution \(x=x_0+tb\), \(y=y_0-ta\) shows that these two solutions are "adjacent" (because \(b-1-b=-1\)).
As \(t\) increases, \(x\) increases and \(y\) decreases, so a non-negative integer solution, if the equation had one, would have to lie between these two solutions. But they are "adjacent": there is no other solution in between.
Hence there cannot be a non-negative integer solution.
-
Then we show that for every integer \(c > ab-a-b\), the equation \(ax+by=c\) has a non-negative integer solution:
Take a solution \((x_0,y_0)\) with \(0\le x_0 < b\) (the form of the general solution shows that this is possible).
Then:
\[ by_0=c-ax_0\ge c-a(b-1)>ab-a-b-ab+a=-b \]So \(b(y_0+1) > 0\), and since \(b>0\), we get \(y_0+1>0\) and therefore \(y_0\ge 0\).
So \((x_0,y_0)\) is a non-negative integer solution.
This completes the proof.
The next theorem shows how Lemma \(2\) extends Theorem \(1\).
Theorem 2
Let \(h_{t+1}>h_t>h_{t-1}\) be positive integers. If \(\gcd(h_{t+1},h_t)=1\), then once the program has executed \(\text{InsertionSort}(h_{t+1})\) and \(\text{InsertionSort}(h_t)\), executing \(\text{InsertionSort}(h_{t-1})\) takes \(O\left(\dfrac{nh_{t+1}h_t}{h_{t-1}} \right)\) time, and for each \(j\), the number of times \(i\) moves is \(O\left(\dfrac{h_{t+1}h_t}{h_{t-1}} \right)\).
Proof of Theorem 2
In what follows, \(A\) is the array before the call to \(\text{InsertionSort}(h_{t-1})\). Fix the index \(j\) of the outer loop; the value to be inserted is \(v=A_j\).
For \(j\le h_{t+1}h_t\), the number of times \(i\) moves is clearly \(O\left(\dfrac{h_{t+1}h_t}{h_{t-1}} \right)\).
So assume \(j>h_{t+1}h_t\) from here on.
For any positive integer \(k\) with \(1\le k\le j-h_{t+1}h_t\), note that \(h_{t+1}h_t-h_{t+1}-h_t<h_{t+1}h_t\le j-k\le j-1\).
Since \(\gcd(h_{t+1},h_t)=1\), Lemma \(2\) gives non-negative integers \(a\) and \(b\) such that \(ah_{t+1}+bh_t=j-k\).
That is:
By Theorem \(1\):
and
Combining the two gives \(A_k=A_{j-ah_{t+1}-bh_t}\le A_j\).
So \(A_k\le A_j\) for every \(1\le k\le j-h_{t+1}h_t\).
In the already processed prefix of the subsequence that \(v\) belongs to, only the elements whose original index lies in \((j-h_{t+1}h_t,j)\) can be greater than \(v\), and there are at most \(\left\lceil\dfrac{h_{t+1}h_t}{h_{t-1}}\right\rceil\) of them. The earlier insertions have only sorted the prefix of this subsequence. So in the pseudocode above, \(i\) decreases by \(h_{t-1}\) each time, and once it has passed these elements it either meets an element no greater than \(v\) or runs off the left end of the array, and the while loop exits. The number of moves is \(O\left(\dfrac{h_{t+1}h_t}{h_{t-1}} \right)\).
With the cost of the moves for each \(j\) established, the total time complexity follows:
This completes the proof.
A close look at the proof of Theorem \(2\) shows that Theorem 1 admits "linear combinations": if \(A\) is sorted with gap \(h\) and also with gap \(k\), then it is still sorted with any gap that is a linear combination of \(h\) and \(k\) with non-negative coefficients. And this "linearity" is exactly what Lemma \(2\) guarantees.
With these two theorems, we can prove Propositions \(1\) and \(2\).
Proof of Proposition 1
Write \(H\) as a sequence:
Shellsort makes its calls in this order: \(\text{InsertionSort}(h_{\lfloor \log_2 n\rfloor}),\text{InsertionSort}(h_{\lfloor \log_2 n\rfloor-1}),\ldots,\text{InsertionSort}(h_2),\text{InsertionSort}(h_1)\).
Assume \(n\ge4\) below. We analyze the complexity in two parts:
-
For the first several gaps, the \(h_t\) with \(h_t\ge \sqrt{n}\), clearly \(\text{InsertionSort}(h_t)\) runs in \(O\left(\dfrac{n^2}{h_t} \right)\).
Take \(k=\min\{t:h_t\ge\sqrt n\}\). Then \(h_k=\Theta(\sqrt n)\), and:
\[ O\left(\frac{n^2}{h_k} \right)=O(n^{3/2}) \]For the \(h_i\) with \(i> k\), since \(2h_i< h_{i+1}\), we get:
\[ O\left(\frac{n^2}{h_i} \right)=O(n^{3/2}/2^{i-k})\,(i>k) \]So the total time complexity of the part with gaps greater than or equal to \(\sqrt n\) is:
\[ \sum_{i=k}^{\lfloor \log_2 n\rfloor}{O(n^{3/2}/2^{i-k})}=O(n^{3/2}) \] -
For the remaining terms, those with \(h_t< \sqrt{n}\), the first two still cost \(O(n^{3/2})\) each, and for the later terms \(h_t\), Theorem \(2\) gives a time complexity of:
\[ O\left(\frac{nh_{t+2}h_{t+1}}{h_t} \right)=O\left(\frac{nh_{t+2}\cdot h_{t+2}/2}{h_{t+2}/4} \right)=O(nh_{t+2}) \]Using the property \(2h_i < h_{i+1}\) once more, the total time complexity of this part is (in the formula below, \(k\) has the same meaning as in the previous case):
\[ 2O(n^{3/2})+\sum_{i=1}^{k-3}{O(nh_{i+1})}=O(n^{3/2})+\sum_{i=1}^{k-3}{O(nh_{k-1}/2^{k-i-3})}=O(n^{3/2})+O(nh_{k-1})=O(n^{3/2}) \]
Altogether, the total time complexity is \(O(n^{3/2})\).
Proof of Proposition 2
Note the following fact: if \(\text{InsertionSort}(2)\) and \(\text{InsertionSort}(3)\) have already been executed, then, because \(2\cdot 3-2-3=1\), Theorem \(2\) shows that for each element only the one immediately before it can be greater than it, and no earlier element is. So the pointer \(i\) needs at most two steps before the while loop exits. In other words, executing \(\text{InsertionSort}(1)\) at this point costs only \(O(n)\).
Going one step further: if \(\text{InsertionSort}(4)\) and \(\text{InsertionSort}(6)\) have already been executed, consider the subsequence formed by all the elements with odd indices and the one formed by the elements with even indices. The two calls amount to executing \(\text{InsertionSort}(2)\) and \(\text{InsertionSort}(3)\) on each of these two subsequences. The same reasoning then applies: executing \(\text{InsertionSort}(2)\) now amounts to executing \(\text{InsertionSort}(1)\) on each of the two subsequences, so making the array sorted with gap \(2\) also takes only time proportional to the sum of the two lengths, that is, \(O(n)\).
Continuing by induction, we get: if \(\text{InsertionSort}(2h)\) and \(\text{InsertionSort}(3h)\) have already been executed, then executing \(\text{InsertionSort}(h)\) also costs only \(O(n)\).
We now analyze the complexity in two parts:
-
For the part with \(h_t>n/3\), executing each \(\text{InsertionSort}(h_t)\) costs \(O(n^2/h_t)\).
Since \(n^2/h_t<3n\), a single insertion sort costs \(O(n)\).
This part contains \(O(\log^2 n)\) gaps, so its time complexity is \(O(n\log^2 n)\).
-
For the part with \(h_t\le n/3\), we have \(3h_t\le n\), so \(\text{InsertionSort}(2h_t)\) and \(\text{InsertionSort}(3h_t)\) have already been executed earlier, and executing \(\text{InsertionSort}(h_t)\) therefore takes \(O(n)\) time.
As before, this part also contains \(O(\log^2 n)\) gaps, so its time complexity is \(O(n\log^2 n)\).
Altogether, the total time complexity is \(O(n\log^2 n)\).
Space complexity
The space complexity of Shellsort is \(O(1)\).
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
1 2 3 4 5 6 7 8 9 10 11 | |
References and notes
-
Shellsort - Wikipedia, the free encyclopedia (in Chinese) ↩
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: partychicken, 24OI-bot, NachtgeistW, Enter-tainer, iamtwz, Xeonacid, Alisahhh, CroMarmot, Menci, Peanut-Tang, Tiphereth-A, ShwStone, shawlleyw, HeRaNO, lailai0916, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.