Shell Sort

#How does it work?

Shell sort improves insertion sort. Insertion sort can only shift elements one place at a time, so bringing a far-away element home takes long.

Shell sort first compares and swaps elements far apart (for example n/2 apart). Small elements jump towards the front in big steps. The gap shrinks every round until it reaches 1.

The final round is a plain insertion sort, but by then the array is nearly sorted, so it finishes quickly.

#Live animation

gap = n / 2
while gap > 0:
  for i = gap to n - 1:
    j = i; while j >= gap and a[j - gap] > a[j]:
      swap(a[j], a[j - gap]); j = j - gap
  gap = gap / 2

#Step by step

1. 01Start with gap = n/2.
2. 02Insertion sort the elements that are gap apart.
3. 03Halve the gap.
4. 04Repeat until the gap is 1.
5. 05The last round (gap = 1) sorts the array completely.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def shell_sort(a: list[int]) -> None:
    """Insertion sort on elements `gap` apart, with the gap halving down to 1."""
    gap = len(a) // 2
    while gap > 0:
        for i in range(gap, len(a)):
            key, j = a[i], i
            while j >= gap and a[j - gap] > key:
                a[j] = a[j - gap]
                j -= gap
            a[j] = key
        gap //= 2


numbers = [5, 1, 4, 2, 8, 3]
shell_sort(numbers)
print(*numbers)

#Complexity

The complexity depends on the gap sequence. With the simple n/2, n/4, … sequence the worst case is O(n²); better sequences (Knuth, Ciura) bring it to O(n^1.5) and below. An exact average-case analysis is still an open problem.

#When to use it?

Used when you want short code, no extra memory, and something much faster than insertion sort on medium-sized arrays. Common in embedded systems and in some libraries' small-array paths.

#Practice

Log in to answer questions and save your progress.