AIOJ

This page briefly introduces Shell sort.

Definition

Shell sort (English: Shell sort), also called diminishing-increment sort, is an improved version of insertion sort. Shell sort is named after its inventor, Donald Shell.

Process

The sort compares and moves non-adjacent records:

Divide the sequence to be sorted into several subsequences (the elements of each subsequence have the same spacing in the original array);
Apply insertion sort to these subsequences;
Reduce the spacing between elements in each subsequence and repeat the above process until the spacing is reduced to $1$ .

Properties

Stability

Shell sort is an unstable sorting algorithm.

Time complexity

The best-case time complexity of Shell sort is $O(n)$ .

The average-case and worst-case time complexities of Shell sort depend on the choice of the gap sequence. Let the gap sequence be $H$ . Two classic choices of $H$ are given below; both reduce the complexity of the sorting algorithm to the $o(n^2)$ level.

Proposition 1

If the gap sequence is $H= \{ 2^k-1\mid k=1,2,\ldots,\lfloor\log_2 n\rfloor \}$ (from large to small), then the time complexity of Shell sort is $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 \}$ (from large to small), then the time complexity of Shell sort is $O(n\log^2 n)$ .

To prove these two propositions, we first give and prove an important theorem that reflects the most important characteristic of Shell sort.

Theorem 1

Once the program has executed $\text{InsertionSort}(h)$ , no matter how the $\text{InsertionSort}$ function is called afterward or how the array $A$ changes, the following properties will always be maintained:

\begin{array}{c} A_1,A_{1+h},A_{1+2h},\ldots \\ A_2,A_{2+h},A_{2+2h},\ldots \\ \vdots \\ A_h,A_{h+h},A_{h+2h},\ldots \end{array}

Next we prove Theorem 1.

We first prove Lemma 1.

Lemma 1

For integers $n,m$ , a positive integer $l$ , and two arrays $X(x_1,x_2,\ldots,x_{n+l}),Y(y_1,y_2,\ldots,y_{m+l})$ satisfying:

y_1 \le x_{n+1},y_2 \le x_{n+2},\ldots,y_l \le x_{n+l}

after sorting the two arrays in ascending order separately, the above requirements still hold.

Proof of Lemma 1

Let the sorted array $X$ be $X'(x'_1,\ldots,x'_{n+l})$ and the sorted array $Y$ be $Y'(y'_1,\ldots,y'_{m+l})$ .

For any $1\le i\le l$ , $x'_{n+i}$ is no smaller than $l-i$ elements in array $X'$ , and is also no smaller than $l-i$ elements in array $X$ (because $X$ and $X'$ have the same multiset of elements).

Therefore, among the multiset $\{x_{n+1},\ldots,x_{n+l} \} \subset X$ , no more than $l-i$ elements are greater than or equal to $x'_{n+i}$ .

Thus at least $i$ elements are smaller than $x'_{n+i}$ . Take $i$ of them and denote them by $x_{n+k_1},x_{n+k_2},\ldots,x_{n+k_i}$ . Then:

y_{k_1}\le x_{n+k_1}\le x'_{n+i},y_{k_2}\le x_{n+k_2}\le x'_{n+i},\ldots,y_{k_i}\le x_{n+k_i}\le x'_{n+i}

Hence $x'_{n+i}$ is at least as large as $i$ elements in $Y$ , and therefore also in $Y'$ , so naturally $y'_i\le x'_{n+i}\,(1\le i\le l)$ .

Returning to the proof of the original proposition:

In fact, we only need to prove that after the immediate next call to $\text{InsertionSort}(k)$ following $\text{InsertionSort}(h)$ , the $h$ subsequences remain sorted; the rest then follows easily by induction. We consider only the next call below:

After executing $\text{InsertionSort}(h)$ , the following groups have been sorted:

\begin{array}{c} A_1,A_{1+h},A_{1+2h},\ldots \\ A_2,A_{2+h},A_{2+2h},\ldots \\ \vdots \\ A_h,A_{h+h},A_{h+2h},\ldots \end{array}

Executing $\text{InsertionSort}(k)$ afterward sorts the following groups:

\begin{array}{c} A_1,A_{1+k},A_{1+2k},\ldots \\ A_2,A_{2+k},A_{2+2k}, \ldots \\ \vdots \\ A_k,A_{k+k},A_{k+2k},\ldots \end{array}

For each $i$ $(1\le i\le \min(h,k))$ , consider the following two groups:

\begin{array}{c} A_i,A_{i+k},A_{i+2k},\ldots \\ \ldots,A_{i+h},A_{i+h+k},A_{i+h+2k},\ldots \end{array}

The reason the second group also begins with 「 $\ldots$ 」 is that there may be elements before it when $i+h\ge k$ .

The second group is the $X$ array in Lemma $1$ , the first group is the $Y$ array, $l$ is the length from $i+h$ in the second group to its end, $n$ is the length of the preceding 「 $\ldots$ 」 in the second group, and $m$ is the number of elements remaining in the first group after removing its first $l$ elements.

Moreover, we have:

A_i\le A_{i+h},A_{i+k}\le A_{i+h+k},\ldots

Therefore, by Lemma $1$ , after $\text{InsertionSort}(k)$ sorts the two groups separately, this relation still holds; that is, $A_i\le A_{i+h}\,(1\le i\le \min(h,k))$ still holds.

If $i>\min(h,k)$ , it is easy to see that adding several $k$ 's to a positive integer $w$ $(1\le w\le \min(h,k))$ can obtain $i$ , so the previous case already implies the proof of this case.

Combining the above discussion, we have $A_i\le A_{i+h}\,(1\le i\le n-h)$ after executing $\text{InsertionSort}(k)$ .

Thus Theorem 1 is proved.

This theorem reveals the key reason why Shell sort can optimize its complexity under a particular set $H$ : throughout the process, it consistently preserves the previous results from being destroyed (that is, the $h$ subsequences remain sorted), greatly reducing the number of movements of pointer $i$ in later calls.

Next we single out and prove a number-theoretic lemma. This theorem became famous in the OI community because of the problem Xiaokai's Confusion. In the proof of Shell sort's complexity, it also greatly extends Theorem $1$ .

Lemma 2

If $a,b$ are both positive integers and coprime, 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

We prove it in two steps:

First prove that the equation $ax+by=ab-a-b$ has no solution where $x,y$ are both non-negative integers:

Without the non-negative-integer restriction, two solutions are readily obtained: $(b-1,-1),(-1,a-1)$ .

From the general solution $x=x_0+tb,y=y_0-ta$ , it is easy to see that the two solutions above are 「adjacent」 (because $b-1-b=-1$ ).

As $t$ increases, $x$ increases and $y$ decreases. Therefore, if the equation had a non-negative integer solution, it would have to lie between these two solutions, but these two solutions are 「adjacent」, with no other solution between them.

Hence no non-negative integer solution exists.
Next prove that for every integer $c > ab-a-b$ , the equation $ax+by=c$ has a non-negative integer solution:

Find a solution $(x_0,y_0)$ satisfying $0\le x_0 < b$ (this can be done from the general solution).

Then:
$by_0=c-ax_0\ge c-a(b-1)>ab-a-b-ab+a=-b$
Therefore $b(y_0+1) > 0$ . Since $b>0$ , $y_0+1>0$ , so $y_0\ge 0$ .

Thus $(x_0,y_0)$ is a solution in non-negative integers.

This completes the proof.

The following theorem reveals how Lemma $2$ extends Theorem $1$ .

Theorem 2

If $\gcd(h_{t+1},h_t)=1$ , then after the program executes $\text{InsertionSort}(h_{t+1})$ and $\text{InsertionSort}(h_t)$ , the time complexity of executing $\text{InsertionSort}(h_{t-1})$ is $O\left(\dfrac{nh_{t+1}h_t}{h_{t-1}} \right)$ , and for each $j$ , the number of movements of $i$ is of order $O\left(\dfrac{h_{t+1}h_t}{h_{t-1}} \right)$ .

Proof of Theorem 2

For the part where $j\le h_{t+1}h_t$ , the number of movements of $i$ is clearly of order $O\left(\dfrac{h_{t+1}h_t}{h_{t-1}} \right)$ .

Therefore, below we assume $j>h_{t+1}h_t$ .

For any positive integer $k$ satisfying $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$ implies that there exist non-negative integers $a,b$ such that $ah_{t+1}+bh_t=j-k$ .

Therefore:

k=j-ah_{t+1}-bh_t

By Theorem $1$ :

A_{j-bh_t}\le A_{j-(b-1)h_t}\le \ldots\le A_{j-h_t}\le A_j

and

A_{j-bh_t-ah_{t+1}}\le A_{j-bh_t-(a-1)h_{t+1}}\le \ldots\le A_{j-bh_t-h_{t+1}}\le A_{j-bh_t}

Combining these gives $A_k=A_{j-ah_{t+1}-bh_t}\le A_j$ .

Therefore, for any $1\le k\le j-h_{t+1}h_t$ , we have $A_k\le A_j$ .

In the Shell-Sort pseudocode, pointer $i$ decreases by $h_{t-1}$ each time. After decreasing $O\left(\dfrac{h_{t+1}h_t}{h_{t-1}} \right)$ times, we have $i\le j-h_{t+1}h_t$ , and therefore $A_i\le A_j$ ; the while-loop condition is not satisfied and the loop exits.

After proving the movement complexity for every $j$ , we obtain the total time complexity:

\sum_{j=h_{t-1}+1}^n{O\left(\frac{h_{t+1}h_t}{h_{t-1}} \right)}=O\left(\frac{nh_{t+1}h_t}{h_{t-1}}\right)

This proves the theorem.

By carefully examining the proof of Theorem $2$ , we can see that Theorem 1 can be linearly combined: if $A$ is ordered with spacing $h$ and also ordered with spacing $k$ , then it remains ordered with any non-negative integer linear combination of $h$ and $k$ . This 「linearity」 is guaranteed by Lemma $2$ .

With these two theorems, we can prove Propositions $1$ and $2$ .

Proof of Proposition 1

Write $H$ in sequence form:

H(h_1=1,h_2=3,h_3=7,\ldots,h_{\lfloor \log_2 n\rfloor}=2^{\lfloor \log_2 n\rfloor}-1)

The execution order of Shell sort is: $\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)$ .

Analyze the complexity in two parts:

For the initial terms satisfying $h_t\ge \sqrt{n}$ , of which the terms are $h_t$ , the time complexity of $\text{InsertionSort}(h_t)$ is clearly $O\left(\dfrac{n^2}{h_t} \right)$ .

Consider the term $h_k$ closest to $\sqrt{n}$ :
$O\left(\frac{n^2}{h_t} \right)=O(n^{3/2})$
For $i> k$ terms $h_i$ , since $2h_i< h_{i+1}$ , we obtain:
$O\left(\frac{n^2}{h_i} \right)=O(n^{3/2}/2^{i-k})\,(i>k)$
Thus, the total time complexity of the part at least $\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 satisfying $h_t< \sqrt{n}$ , the complexity of the first two terms is still $O(n^{3/2})$ . For the later terms $h_t$ , Theorem $2$ gives:
$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}$ again, the total time complexity of this part is (where $k$ retains its meaning from 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})$

Therefore, the total time complexity is $O(n^{3/2})$ .

Proof of Proposition 2

Observe 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 previous adjacent element may be greater than it; all preceding elements are smaller than it. Therefore, pointer $i$ needs at most two iterations to exit the while loop. In other words, executing $\text{InsertionSort}(1)$ at this point has complexity $O(n)$ .

More generally, if $\text{InsertionSort}(4)$ and $\text{InsertionSort}(6)$ have already been executed, consider the subsequence of elements with odd indices and the subsequence of elements with even indices. This is equivalent to executing $\text{InsertionSort}(2)$ and $\text{InsertionSort}(3)$ on these two subsequences separately. Thus, executing $\text{InsertionSort}(2)$ now is equivalent to executing $\text{InsertionSort}(1)$ on each of the two subsequences; it only needs the order of the sum of the two sequence lengths, namely $O(n)$ complexity, to make the array ordered with spacing $2$ .

Continuing by induction, we obtain: if $\text{InsertionSort}(2h)$ and $\text{InsertionSort}(3h)$ have already been executed, then executing $\text{InsertionSort}(h)$ also has complexity only $O(n)$ .

Analyze the complexity in two parts:

For the terms with $h_t>n/3$ , each $\text{InsertionSort}(h_t)$ has complexity $O(n^2/h_t)$ .

Since $n^2/h_t<3n$ , the complexity of each insertion sort is $O(n)$ .

The number of elements in this part is of order $O(\log^2 n)$ , so its time complexity is $O(n\log^2 n)$ .
For the terms with $h_t\le n/3$ , since $3h_t\le n$ , $\text{InsertionSort}(2h_t)$ and $\text{InsertionSort}(3h_t)$ have already been executed before this. Therefore, executing $\text{InsertionSort}(h_t)$ has time complexity $O(n)$ .

Likewise, the number of elements in this part is also of order $O(\log^2 n)$ , so its time complexity is $O(n\log^2 n)$ .

Therefore, the total time complexity is $O(n\log^2 n)$ .

Space Complexity

The space complexity of Shell sort is $O(1)$ .

Implementation

C++¹

template <typename T>
void shell_sort(T array[], int length) {
  int h = 1;
  while (h < length / 3) {
    h = 3 * h + 1;
  }
  while (h >= 1) {
    for (int i = h; i < length; i++) {
      for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
        std::swap(array[j], array[j - h]);
      }
    }
    h = h / 3;
  }
}

Python

def shell_sort(array, length):
    h = 1
    while h < length / 3:
        h = int(3 * h + 1)
    while h >= 1:
        for i in range(h, length):
            j = i
            while j >= h and array[j] < array[j - h]:
                array[j], array[j - h] = array[j - h], array[j]
                j -= h
        h = int(h / 3)

References and notes

Footnotes

Shell sort - Wikipedia, the free encyclopedia ↩