Shell Sort in Python: Gaps, Code, and Complexity

Quick answer: Shell sort is an in-place comparison sort that performs insertion-sort passes over decreasing gaps. It is valuable for learning how gap sequences reduce distant inversions, but ordinary Python application code should normally use the optimized built-in sorted() or list.sort().

Shell sort is an in-place comparison sorting algorithm that improves insertion sort by moving far-apart elements before doing smaller local passes. Instead of comparing only adjacent items from the start, Shell sort uses a gap sequence, sorts elements that are that gap apart, then keeps shrinking the gap until the final insertion-sort pass.

In everyday Python programs, use list.sort() or sorted(). Shell sort is most useful for learning how gap-based sorting works or for environments where you must implement an in-place educational sorting algorithm yourself.

How Shell Sort Works

Shell sort repeatedly performs a gapped insertion sort. The first pass uses a large gap, so values can move closer to their final position quickly. Later passes use smaller gaps. The final gap is always 1, which finishes the sort like insertion sort on a nearly sorted list.

NIST’s Dictionary of Algorithms and Data Structures has a concise Shell sort definition. The important implementation detail is the gap sequence. This guide uses the simple halving sequence: n // 2, then half again until the gap becomes 0.

Shell Sort Code in Python

The function below sorts the list in place and also returns it for convenience.

def shell_sort(values):
    gap = len(values) // 2

    while gap > 0:
        for index in range(gap, len(values)):
            current = values[index]
            position = index

            while position >= gap and values[position - gap] > current:
                values[position] = values[position - gap]
                position -= gap

            values[position] = current

        gap //= 2

    return values

numbers = [23, 12, 1, 8, 34, 54, 2, 3]
print(shell_sort(numbers))

This is similar to insertion sort, but the inner loop compares values[position - gap] instead of only the immediately previous element. For the smaller adjacent-only version, see PythonPool’s insertion sort in Python guide.

Dry Run with Gaps

For eight values, the first gap is 4. The algorithm compares positions 0 and 4, 1 and 5, and so on. Then it repeats with gap 2, then gap 1.

def shell_sort_with_gaps(values):
    gap = len(values) // 2
    gaps_used = []

    while gap > 0:
        gaps_used.append(gap)
        for index in range(gap, len(values)):
            current = values[index]
            position = index

            while position >= gap and values[position - gap] > current:
                values[position] = values[position - gap]
                position -= gap

            values[position] = current
        gap //= 2

    return gaps_used, values

print(shell_sort_with_gaps([23, 12, 1, 8, 34, 54, 2, 3]))

Tracing the gaps makes the algorithm easier to debug. If your implementation throws index errors while moving through the list, PythonPool’s list index out of range article explains the usual boundary mistakes.

Descending Shell Sort

To sort in descending order, flip the comparison in the inner loop from greater-than to less-than.

def shell_sort_descending(values):
    gap = len(values) // 2

    while gap > 0:
        for index in range(gap, len(values)):
            current = values[index]
            position = index

            while position >= gap and values[position - gap] < current:
                values[position] = values[position - gap]
                position -= gap

            values[position] = current

        gap //= 2

    return values

print(shell_sort_descending([23, 12, 1, 8, 34, 54, 2, 3]))

For normal application code, Python's built-in sort is clearer and faster. The official Python sorting HOWTO explains list.sort(), sorted(), keys, and reverse sorting.

Shell Sort Complexity

Shell sort's time complexity depends on the gap sequence. With the simple halving sequence used here, worst-case behavior is commonly discussed around quadratic growth. Better gap sequences can improve practical performance, but the details are beyond a beginner implementation.

Use timeit for small local comparisons instead of guessing. Python's official timeit documentation explains why it is safer than casual timing.

Compare with Python's Built-in Sort

Python's built-in sorting is highly optimized and stable. Shell sort is educational, but built-in sorting should be the default for real work.

numbers = [23, 12, 1, 8, 34, 54, 2, 3]

print(sorted(numbers))
numbers.sort(reverse=True)
print(numbers)

The official Python list data structure documentation covers list.sort() with other common list methods.

Common Mistakes

• Forgetting to reduce the gap, which creates an infinite loop.
• Stopping before gap 1, leaving the list only partially sorted.
• Using position - 1 instead of position - gap inside the gapped insertion loop.
• Claiming one fixed average complexity without naming the gap sequence.
• Using Shell sort in production where Python's built-in Timsort is the better choice.

For other sorting examples on PythonPool, compare bubble sort in Python, bitonic sort, and sorting dictionaries by key.

When Shell Sort Is Useful

Shell sort is a good teaching algorithm because it shows how a small change to insertion sort can reduce the number of long-distance shifts. It also uses constant extra memory, so the implementation is easy to reason about. Still, for production Python code, the built-in sorting functions are clearer, stable, and maintained by the Python runtime.

Understand The Gap Pass

For a gap, compare elements separated by that distance and perform insertion-like moves within each interleaved subsequence. After the gap reaches one, the final pass is ordinary insertion sort over an almost-sorted list.

Choose A Gap Sequence

The sequence affects performance and is part of the algorithm's behavior. A simple halving sequence is easy to teach, while other sequences can improve practical results; state which one the implementation uses.

Keep The Sort In Place

A typical implementation mutates the list and returns None, like list.sort(). If callers need the original preserved, copy it deliberately or expose a separate function that returns a new list.

Explain Complexity Carefully

Shell sort's time complexity depends on the gap sequence and input. Avoid claiming one universal bound without naming the sequence, and include space usage and stability in the comparison.

Compare Built-in Sorting

Python's built-in sorting is highly optimized, stable, and designed for application use. A custom Shell sort is appropriate for education, algorithm exercises, or a measured constrained environment, not as a default replacement.

Test Sorting Invariants

Test empty, one-item, sorted, reverse-sorted, duplicate, negative, and already-partially-sorted inputs. Check that the result is ordered and that the mutation or return contract is consistent.

The official Python sorting HOWTO explains built-in sorting choices. Related Python Pool references include lists and tests.

For related sorting choices, compare list behavior, ordering tests, and built-in sorting before using a custom gap sequence.

Frequently Asked Questions

What is Shell sort?

Shell sort is an in-place comparison sort that performs insertion-sort passes over elements separated by a sequence of decreasing gaps.

Why does Shell sort use gaps?

Large gaps move out-of-place values closer to their final positions before the final insertion-sort pass handles local disorder.

Is Shell sort stable?

Typical in-place Shell sort is not stable because gap moves can reorder equal values.

Should I use Shell sort instead of sorted()?

Use sorted() or list.sort() for ordinary Python application code; Shell sort is mainly useful for learning, constrained environments, or a measured specialized need.