Shell Sort Algorithm with Example

What is Shell Sort?

Shell Sort, also called Shell’s method, is an efficient in-place comparison-based sorting algorithm. Named after Donald Shell, who introduced the idea in 1959, it is a generalized extension of insertion sort that overcomes its quadratic behavior on scattered data.

The fundamental idea is to group elements that are far apart, sort each group using insertion sort, and shrink the gap step by step until it reaches one. By then the array is nearly sorted.

This gap, the interval, follows a chosen sequence such as Shell’s original, Knuth’s, Hibbard’s, or Sedgewick’s. Shell’s original is n/2, n/4, ..., 1.

Shell Sort Algorithm

Step 1) Initialize the interval value h = n/2, where n is the size of the array.

Step 2) Place all the elements within a distance of the interval h into a sublist.

Step 3) Sort each sublist using insertion sort.

Step 4) Set a new interval h = h/2.

Step 5) If h > 0, return to Step 2. Otherwise, go to Step 6.

Step 6) The resulting array is now fully sorted.

How Shell Sort Works

In insertion sort, elements move by only one position at a time. Shell Sort instead divides the array into widely spaced sublists based on the interval and runs insertion sort on each sublist.

As the interval shrinks, the sublist size grows. Because earlier passes leave the data partially sorted, smaller intervals require far fewer swaps than running insertion sort from scratch. The figure below illustrates one Shell Sort pass.

Working of Shell Sort Algorithm with Example

Let’s sort the array below using Shell Sort.

Step 1) The array size is 8, so the initial interval value is h = 8/2 = 4.

Step 2) Group elements four positions apart. Sublists: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Step 3) Sort each sublist using insertion sort. A temporary variable holds the value being placed while elements shift. After the swaps, the array looks like this.

Step 4) Decrease the interval. The new interval is h = 4/2 = 2.

Step 5) Because 2 > 0, return to Step 2 and group elements two positions apart: {1, 5, 8, 7} and {4, 2, 6, 3}.

Sort the first sublist. The array becomes:

After sorting the second sublist:

Decrease the interval again to h = 2/2 = 1. With a gap of one, Shell Sort runs a final insertion-sort pass over the whole array, as shown below.

Step 6) Dividing the interval again yields 0. The array is now fully sorted:

Pseudo-Code for Shell Sort

Start
Input array a of size n
for (interval = n / 2; interval > 0; interval /= 2)
    for (i = interval; i < n; i += 1)
        temp = a[i];
        for (j = i; j >= interval && a[j - interval] > temp; j -= interval)
            a[j] = a[j - interval];
        a[j] = temp;
End

Shell Sort Program in C/C++

Input:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

Output:

Sorted Output:

1 2 3 4 5 6 7 8

Shell Sort Example in Python

Input:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

Output:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Applications of Shell Sort

Shell Sort still appears in modern systems where stack space or simplicity matters.

• The Linux kernel uses Shell Sort in places where avoiding a call stack matters.
• uClibc embedded C library uses Shell Sort to keep memory usage low.
• bzip2 uses Shell Sort to avoid deep recursion during block-sorting.
• Embedded firmware favors Shell Sort for small datasets where recursion is restricted.

Advantages and Disadvantages of Shell Sort

Shell Sort Complexity Analysis

Time Complexity of Shell Sort

The time complexity of Shell Sort depends on the gap sequence used.

In the best case, when the array is already nearly arranged, each pass needs only a logarithmic number of tests, giving O(n log n).

In the worst case, the array is arranged so elements need the maximum comparisons, and the final increment dominates at O(n^2) with Shell’s original sequence.

1. Best-case complexity: O(n log n)
2. Average-case complexity: O(n log n) to O(n^(4/3)) depending on the gap sequence
3. Worst-case complexity: O(n^2) with Shell’s original sequence

The best general-purpose gap sequence is still an open research question, although Sedgewick and Ciura sequences perform well in practice.

Shell Sort Space Complexity

Shell Sort does not require auxiliary arrays, so the space complexity is O(1) regardless of input size, which is one of its strongest practical advantages.

FAQs