Shell Sort in Data Structure — Algorithm, Visualization and Complexity

Shell Sort is an optimization of Insertion Sort that allows the exchange of elements that are far apart. It works by first sorting elements that are a certain 'gap' distance apart, then progressively reducing the gap until it becomes 1 (a final regular insertion sort pass).

How It Works (Visualization)

For an array of size 8 with an initial gap of 4, elements at positions (0,4), (1,5), (2,6), (3,7) are compared and sorted first. The gap is then reduced (commonly halved, e.g., to 2), and the process repeats with smaller sub-groups, until the gap becomes 1, performing a final full insertion sort pass on the now mostly-sorted array.

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

Complexity

Advantages

• Significantly faster than plain Insertion Sort or Bubble Sort for medium-sized arrays.
• In-place — requires only O(1) extra space.
• Simple to implement compared to Merge Sort or Quick Sort.

Applications

• Sorting medium-sized datasets where simplicity and low memory use matter.
• Embedded systems with limited memory.
• Used historically in the uClibc library's qsort implementation for small arrays.