Shell Sort Algorithm | Working, Code, Complexity

Shell Sort is an in-place comparison-based sorting algorithm invented by Donald Shell in 1959. It is a improved version of Insertion Sort that works faster, especially for large lists. As it was invented by Donald Shell in 1959, that’s why it’s called Shell Sort.

The main idea is to compare elements that are far apart first, instead of only comparing nearby elements (like in Insertion Sort). As the algorithm continues, the gap between compared elements becomes smaller until it becomes 1, at that point, the algorithm behaves like normal Insertion Sort, but on an almost-sorted list, which is much faster.

This approach allows elements to move faster towards their correct positions, significantly reducing the number of shifts required compared to standard insertion sort, especially on larger datasets.

How Shell Sort Works?

Shell Sort is an improved version of Insertion Sort that becomes faster by comparing elements that are far apart instead of only comparing neighboring elements. It introduces a concept called the gap, which controls how far apart the compared elements are.

What Is the Gap in Shell Sort?

The gap is a number that tells how far two elements are when comparing them.

• At the beginning, the gap is large.
• As the algorithm runs, the gap keeps getting smaller.
• When the gap finally becomes 1, the algorithm behaves exactly like Insertion Sort — but by this time the list is already nearly sorted.

This makes Shell Sort much faster than a normal Insertion Sort.

How Shell Sort Works (Step-by-Step)

Here’s the complete process in simple words:

1. Choose an initial gap

Usually, the gap is set as:

• n/2 (half the size of the array)

2. Compare elements that are gap distance apart

Example:
If gap = 4, compare positions:

• 0 with 4
• 1 with 5
• 2 with 6
• … and so on

If an element at the right position is smaller, they are swapped.

3. Perform Insertion Sort on each gap-based group

For every gap value, the array is divided into smaller “virtual” sublists. Each sublist goes through a gapped insertion sort, which brings elements closer to their correct positions.

4. Reduce the gap and repeat

Common patterns:

• Divide the gap by 2
• Or use advanced sequences like Knuth’s sequence for better performance

Each time the gap becomes smaller, the array becomes more sorted.

5. Final pass when gap = 1

This is a normal Insertion Sort, but with a big advantage:
Most elements are already near their correct place → meaning very few comparisons and swaps.

Why Shell Sort Is Faster than Insertion Sort?

Insertion Sort is slow mainly because elements move one position at a time.

Shell Sort lets elements jump across the array using large gaps.
This reduces the total number of movements and makes the final sorting extremely efficient.

Shell Sort Algorithm

1. Initialize the gap
   • Let the total number of elements be n.
   • Set the initial gap as gap = n / 2.
   • The gap tells how far apart two elements should be when compared.
2. Repeat until the gap becomes 0
   • While gap > 0, do the following steps:
   a. Traverse the array from index = gap to n-1
   • For each element at position i, temporarily store it in a variable temp.
   • This element will be placed in its correct position among the elements that are gap distance apart.
   b. Compare and shift elements within the gap
   • Set j = i.
   • While j >= gap and the element at position j - gap is greater than temp:
     • Move the element at j - gap to position j.
     • Decrease j by gap (go back by the gap distance).
   • When this condition fails, insert temp at position j.
   c. Continue for all elements in the array
   • Repeat the process for all remaining elements from index = gap to the end of the array.
   d. Reduce the gap value
   • After completing one full pass, divide the gap by 2 (integer division).
   • Example: if gap = 4, next gap = 2, then 1.
3. Final pass (gap = 1)
   • When the gap becomes 1, the array will go through a normal insertion sort.
   • Since most elements are already close to their correct position, this step will be fast.
4. End of algorithm

Example of Shell Sort

Let’s take an array:

[12, 34, 54, 2, 3]

Step 1: Start

• Number of elements (n) = 5
• Initial gap = n / 2 = 5 / 2 = 2

This means we will compare and sort elements that are 2 positions apart.

Step 2: Sorting with Gap = 2

Now, we start from the element at index 2 and move to the end of the array, performing Insertion Sort logic between elements that are 2 apart.

Compare elements 2 apart:

1. Compare arr[0] and arr[2] → (12 and 54)
   • 12 < 54 → already in correct order
   • No change needed.
   • Array: [12, 34, 54, 2, 3]
2. Compare arr[1] and arr[3] → (34 and 2)
   • 34 > 2 → not in order, so swap them.
   • After swap: [12, 2, 54, 34, 3]
3. Compare arr[2] and arr[4] → (54 and 3)
   • 54 > 3 → not in order, so swap them.
   • After swap: [12, 2, 3, 34, 54]

Now, after sorting with gap = 2, the array looks like this:

[12, 2, 3, 34, 54]

You can see it’s already partially sorted — the smaller numbers are starting to move to the front.

Step 3: Reduce the Gap

Now we reduce the gap.
gap = gap / 2 = 2 / 2 = 1

When the gap becomes 1, it’s time for the final pass — a normal Insertion Sort.

Step 4: Sorting with Gap = 1

Now we will compare and sort elements that are 1 apart (just like regular Insertion Sort).
The array currently is [12, 2, 3, 34, 54].

Let’s sort step-by-step:

1. Compare 12 and 2
   • 12 > 2 → swap
   • Array becomes [2, 12, 3, 34, 54]
2. Compare 12 and 3
   • 12 > 3 → swap
   • Array becomes [2, 3, 12, 34, 54]
3. Compare 12 and 34
   • 12 < 34 → no swap
4. Compare 34 and 54
   • 34 < 54 → no swap

Now, the array is completely sorted.

Final Sorted Array

[2, 3, 12, 34, 54]

Shell Sort Implementation Using C++

#include <iostream>
using namespace std;

// Function to perform Shell Sort
void shellSort(int arr[], int n) {
    // Start with a big gap, then reduce it
    for (int gap = n / 2; gap > 0; gap /= 2) {

        // Do a gapped insertion sort for this gap size
        for (int i = gap; i < n; i++) {
            int temp = arr[i]; // Element to be compared and inserted
            int j = i;

            // Shift earlier gap-sorted elements up until the correct position for arr[i] is found
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }

            // Put temp (the original arr[i]) in its correct location
            arr[j] = temp;
        }
    }
}

int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    // Calling Shell Sort function
    shellSort(arr, n);

    cout << "Sorted array:   ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

Output

Original array: 12 34 54 2 3
Sorted array:   2 3 12 34 54

Explanation of Code

The above C++ program uses the Shell Sort algorithm to arrange an array in ascending order. It starts by including <iostream> and using the std namespace for easy input and output. The shellSort(int arr[], int n) function takes an array and its size. It begins by setting a gap as half of the array size (gap = n / 2) and keeps reducing it by half after each pass.

For every gap, it performs a modified insertion sort where elements that are gap positions apart are compared. If an earlier element is greater than the current one, it is shifted forward until the right place for the current element (temp) is found. When the gap becomes 1, a normal insertion sort is done on the nearly sorted array, finishing the sorting quickly.

In the main() function, the array {12, 34, 54, 2, 3} is defined, its size is calculated, and the shellSort() function is called to sort it. The original and final sorted arrays are printed as output.

Time and Space Complexity of Shell Sort

Time Complexity of Shell Sort

Case	Time Complexity
Best Case	O(n log n)
Average Case	O(n(3/2))
Worst Case	O(n²)

Space Complexity of Shell Sort

Case	Space Complexity
Best Case	O(1)
Average Case	O(1)
Worst Case	O(1)

Advantages of Shell Sort

• Simple and Easy to Implement: Compared to complex algorithms like Quick Sort or Merge Sort, Shell Sort is easier to understand and code.
• Faster than Insertion Sort: Shell Sort is an improved version of Insertion Sort. It works faster because it compares and swaps elements that are far apart, reducing the number of overall shifts.
• Efficient for Medium-Sized Data: While not the fastest for huge datasets, Shell Sort performs very well for medium-sized arrays where simpler algorithms like Bubble or Insertion Sort would take longer.
• In-Place Sorting: It does not require any extra memory; sorting happens within the same array, making it memory-efficient.
• Performs Well on Partially Sorted Data: If the data is already nearly sorted, Shell Sort quickly brings the remaining elements to their correct positions.

Disadvantages of Shell Sort

• Limited Theoretical Understanding: Unlike other algorithms with well-defined complexity bounds, Shell Sort lacks a universally optimal formula for its efficiency.
• Complex Time Analysis: The time complexity of Shell Sort depends heavily on the choice of gap sequence, making it difficult to analyze or predict its exact running time.
• Not Stable: Shell Sort is not a stable sorting algorithm, meaning it may change the relative order of equal elements, which can be an issue in some applications.
• Less Efficient for Large Data: For very large datasets, advanced algorithms like Merge Sort or Quick Sort perform better in terms of speed and scalability.
• Gap Sequence Dependency: The performance of Shell Sort can vary significantly based on the gap sequence chosen; a poor choice of gaps can make it perform close to Insertion Sort.

Applications of Shell Sort

1. When Memory Is Very Limited (In-Place Sorting)

Shell Sort works inside the same array without using extra memory.
So it is useful in systems with low RAM, embedded devices, or old hardware where memory is expensive.

2. Useful for Medium-Sized Datasets

Shell Sort is not the fastest for very large data, but it is excellent for small and medium-sized arrays (few thousands of elements).
It performs faster than simple algorithms like Insertion Sort or Bubble Sort.

3. When Data Is Already Almost Sorted

Shell Sort becomes extremely fast when the dataset is partially sorted, because the final pass (gap = 1) needs very few operations.
This makes it great for applications where the list is updated frequently but changes only slightly.

4. Good for Real-Time Systems (Predictable Performance)

Shell Sort has more predictable running time than algorithms like Quick Sort, which can degrade to O(n²).
In real-time systems, predictability is important, so Shell Sort is preferred over Quick Sort.

5. Efficient for Arrays, Not Linked Lists

Since Shell Sort works by jumping long distances using gaps, it is more suitable for arrays, where index access is constant time.
Therefore, it is used in systems or tools that store data in arrays and need fast internal sorting.