Implementing Shell Sort: From Theory to Practical Code

Source: Dev.to

What is Shell Sort?

Shell sort is an improvement over insertion sort, which is one of the fundamental sorting algorithms. Insertion sort compares and inserts adjacent elements in a given array.
By contrast, Shell sort repeatedly performs insertion‑like operations on elements that are separated by a fixed gap, gradually reducing the gap size. When the gap becomes 1, the algorithm behaves exactly like insertion sort.

This raises an important question: if Shell sort ultimately becomes insertion sort, where does the improvement come from?

Complexity Overview

• Insertion sort

  • Time complexity: (O(n^2)) to (O(n))
  • Space complexity: (O(1))

• Shell sort (depending on the gap sequence)

  • Time complexity: approximately (O(n^{1.3})) to (O(n \log n))
  • Space complexity: (O(1))

In practice, the performance difference becomes noticeable when the input size exceeds around 1,000 elements.

Example Problem

You have the integer scores of 10,000 engineers arranged in random order and need to pair engineers whose scores are close to each other.

1. Sort the engineers by score.
2. Pair adjacent elements in the sorted list.

Using insertion sort for step 1 can require up to one billion operations in the worst case ((O(n^2))). Shell sort reduces the average time to roughly (O(n^{1.3})) to (O(n \log n)), depending on the gap sequence.

Insertion Sort Approach

For each index (i) from 1 to (n-1):

1. Store the value of (A_i) in a temporary variable x.
2. While (A_j > x) (with (j = i-1, i-2, \dots)), shift (A_j) one position to the right.
3. Insert x into the correct position.

Insertion sort can be viewed as a special case of Shell sort where the gap size is 1.

Shell Sort Approach

1. Choose an initial gap value g.
2. For each index (i) from g to (n-1):
   • Store (A_i) in a temporary variable x.
   • While (A_j > x) (with (j = i-g, i-2g, \dots)), shift (A_j) to (A_{j+g}).
   • Insert x into (A_{j+g}).
3. Reduce the gap and repeat steps 2‑3 until the gap becomes 1.

Implementation of Shell Sort

Pattern 1: Gap Sequence Provided as Input

def insertion_sort(array, n, gap):
    for i in range(gap, n):
        # Store the value of A[i] in a temporary variable x
        x = array[i]
        j = i - gap
        while j >= 0 and array[j] > x:
            # Shift A[j] to A[j+gap]
            array[j + gap] = array[j]
            j -= gap
        # Insert x into A[j+gap]
        array[j + gap] = x

def shell_sort(array, n, gap_sequence):
    for gap in gap_sequence:
        insertion_sort(array, n, gap)

n denotes the number of elements in the array.

Pattern 2: Gap Sequence Generated Within the Algorithm

def insertion_sort(array, n, gap):
    for i in range(gap, n):
        x = array[i]
        j = i - gap
        while j >= 0 and array[j] > x:
            array[j + gap] = array[j]
            j -= gap
        array[j + gap] = x

def shell_sort(array, n):
    # Create the gap sequence (using the classic n//2, n//4, …, 1 scheme)
    gap_sequence = []
    gap = n // 2
    while gap > 0:
        gap_sequence.append(gap)
        gap //= 2
    if not gap_sequence:
        gap_sequence.append(1)

    for gap in gap_sequence:
        insertion_sort(array, n, gap)

The optimal gap sequence for Shell sort remains an open problem. If you notice any mistakes, feel free to point them out.