Shell Sort

This page provides a brief introduction to Shell sort.

Definition

Shell sort, also known as the diminishing increment sort, is an improved version of Insertion Sort. It is named after its inventor, Donald Shell.

Process

The sorting process compares and moves non-adjacent records:

Divide the sequence to be sorted into several subsequences (elements in each subsequence have the same spacing in the original array);
Perform insertion sort on 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 optimal time complexity of Shell sort is \(O(n)\).

The average and worst-case time complexities of Shell sort depend on the chosen gap sequence. Let the gap sequence be \(H\). Two classic choices for \(H\) are given below, both of which reduce the algorithm's complexity 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 descending order), 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 \}\) (in descending order), then the time complexity of Shell sort is \(O(n\log^2 n)\).

To prove these propositions, we first present and prove an important theorem that reflects the main characteristic of Shell sort.

Theorem 1

Once the program executes \(\text{InsertionSort}(h)\), regardless of subsequent calls to \(\text{InsertionSort}\) or changes to array \(A\), the following property 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} \]

Then, after sorting both arrays in ascending order, the above condition still holds.

Proof of Lemma 1

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

For any \(1\le i\le l\), \(x'_{n+i}\) is less than or equal to \(l-i\) elements in array \(X'\), and also less than or equal to \(l-i\) elements in array \(X\) (since \(X\) and \(X'\) have the same multiset of elements).

Then, in the multiset \(\{x_{n+1},\ldots,x_{n+l} \} \subset X\), the number of elements greater than or equal to \(x'_{n+i}\) is at most \(l-i\).

Thus, there are at least \(i\) elements less than \(x'_{n+i}\). Take \(i\) of them, denoted as \(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} \]

Therefore, \(x'_{n+i}\) is at least greater than or equal to \(i\) elements in \(Y\), i.e., \(Y'\). Hence, \(y'_i\le x'_{n+i}\,(1\le i\le l)\).

Returning to the proof of the original proposition:

We only need to prove that immediately after calling \(\text{InsertionSort}(h)\) and then calling \(\text{InsertionSort}(k)\), the \(h\) subsequences remain ordered. The rest follows easily by induction. Consider only the next call:

After executing \(\text{InsertionSort}(h)\), the following groups are 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} \]

Subsequently, executing \(\text{InsertionSort}(k)\) will sort 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 "\(\ldots\)" in the second group is because \(i+h\ge k\) may hold, so there may be elements before it.

Then the second group is the \(X\) array in Lemma \(1\), the first group is the \(Y\) array, \(l\) is the length of the second group from \(i+h\) to the end, \(n\) is the length of the "\(\ldots\)" before the second group, and \(m\) is the number of elements remaining in the first group after removing the first \(l\) elements.

Since:

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

By Lemma \(1\), after executing \(\text{InsertionSort}(k)\) to sort the two groups separately, this relationship still holds, i.e., \(A_i\le A_{i+h}\,(1\le i\le \min(h,k))\).

If \(i>\min(h,k)\), it is easy to see that by taking a positive integer \(w\) \((1\le w\le \min(h,k))\) and adding multiples of \(k\), we can obtain \(i\). The previous case already implies the proof for this case.

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

Thus, Theorem 1 is proved.

This theorem reveals the key to optimizing the complexity of Shell sort under specific sets \(H\). Throughout the process, it consistently preserves previous achievements (i.e., the \(h\) subsequences remain ordered), thereby significantly reducing the number of moves of pointer \(i\) in subsequent calls.

Next, we prove a number theory lemma separately. This lemma is well-known in the OI community due to the problem 小凯的疑惑. In the proof of Shell sort's complexity, it greatly extends Theorem \(1\).

Lemma 2

If \(a,b\) are 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

The proof is divided into two steps:

First, prove that the equation \(ax+by=ab-a-b\) has no non-negative integer solutions for \(x\) and \(y\):

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

From the general solution form \(x=x_0+tb,y=y_0-ta\), these two solutions are "adjacent" (since \(b-1-b=-1\)).

As \(t\) increases, \(x\) increases and \(y\) decreases. If there were a non-negative integer solution, it would lie between these two solutions, but they are "adjacent" with no other solutions in between.

Thus, no non-negative integer solution exists.
Next, prove that for any integer \(c > ab-a-b\), the equation \(ax+by=c\) has a non-negative integer solution:

We find a solution \((x_0,y_0)\) such that \(0\le x_0 < b\) (this can be done using the general solution expression).

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\), \(y_0+1>0\), hence \(y_0\ge 0\).

Thus, \((x_0,y_0)\) is a non-negative integer solution.

This completes the proof.

The following theorem shows how Lemma \(2\) extends Theorem \(1\).

Theorem 2

If \(\gcd(h_{t+1},h_t)=1\), then after executing \(\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 moves of \(i\) is \(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 moves of \(i\) is clearly \(O\left(\dfrac{h_{t+1}h_t}{h_{t-1}} \right)\).

Thus, assume \(j>h_{t+1}h_t\) in the following.

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\), by Lemma \(2\), there exist non-negative integers \(a,b\) such that: \(ah_{t+1}+bh_t=j-k\).

Thus:

\[ k=j-ah_{t+1}-bh_t \]

By Theorem \(1\), we have:

\[ 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 the above, we have: \(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\), \(A_k\le A_j\).

In the Shell-Sort pseudocode, pointer \(i\) decreases by \(h_{t-1}\) each time. After \(O\left(\dfrac{h_{t+1}h_t}{h_{t-1}} \right)\) decreases, \(i\le j-h_{t+1}h_t\), so \(A_i\le A_j\), and the while loop condition fails, exiting.

After proving the move complexity for each \(j\), the total time complexity is:

\[ \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 completes the proof.

Carefully observing the proof of Theorem \(2\), we can see that Theorem 1 allows "linear combinations": if \(A\) is ordered with spacing \(h\) and also ordered with spacing \(k\), then it remains ordered under non-negative linear combinations 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\) as a sequence:

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

Shell-Sort executes in the 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)\).

Analyze the complexity in two parts:

For the first few \(h_t\) satisfying \(h_t\ge \sqrt{n}\), 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\), since \(2h_i< h_{i+1}\), we have:

\[ O\left(\frac{n^2}{h_i} \right)=O(n^{3/2}/2^{i-k})\,(i>k) \]

Thus, the total time complexity for the part 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 satisfying \(h_t< \sqrt{n}\), the first two terms still have complexity \(O(n^{3/2})\). For the later terms \(h_t\), by Theorem \(2\), the time complexity is:

\[ 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 for 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}) \]

In summary, the total time complexity is \(O(n^{3/2})\).

Proof of Proposition 2

Note a fact: if \(\text{InsertionSort}(2)\) and \(\text{InsertionSort}(3)\) have been executed, then because \(2\cdot 3-2-3=1\), by Theorem \(2\), each element may only be greater than its immediately preceding element, and all earlier elements are less than it. Thus, pointer \(i\) needs at most two moves to exit the while loop. That is, executing \(\text{InsertionSort}(1)\) now reduces the complexity to \(O(n)\).

Further: if \(\text{InsertionSort}(4)\) and \(\text{InsertionSort}(6)\) have been executed, consider the subsequence of elements with odd indices and the subsequence with even indices. This is equivalent to executing \(\text{InsertionSort}(2)\) and \(\text{InsertionSort}(3)\) on these two subsequences, respectively. Similarly, executing \(\text{InsertionSort}(2)\) now is equivalent to executing \(\text{InsertionSort}(1)\) on each subsequence, requiring only \(O(n)\) complexity to make the array 2-gap ordered.

By continuous induction, we obtain: if \(\text{InsertionSort}(2h)\) and \(\text{InsertionSort}(3h)\) have been executed, then the complexity of executing \(\text{InsertionSort}(h)\) is also \(O(n)\).

Next, analyze the complexity in two parts:

For the part where \(h_t>n/3\), the complexity of each \(\text{InsertionSort}(h_t)\) is \(O(n^2/h_t)\).

Since \(n^2/h_t<3n\), the complexity of a single insertion sort is \(O(n)\).

The number of such elements is \(O(\log^2 n)\), so the time complexity for this part is \(O(n\log^2 n)\).
For the part where \(h_t\le n/3\), since \(3h_t\le n\), \(\text{InsertionSort}(2h_t)\) and \(\text{InsertionSort}(3h_t)\) have already been executed. Thus, the time complexity of executing \(\text{InsertionSort}(h_t)\) is \(O(n)\).

Again, the number of such elements is \(O(\log^2 n)\), so the time complexity for this part is \(O(n\log^2 n)\).

In summary, the total time complexity is \(O(n\log^2 n)\).

Space Complexity

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

Implementation

C++¹Python

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;
  }
}

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

Shell sort - Wikipedia ↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用