A practical guide to comb sort and its gap sequence

Comb sort is a simple comparison-sorting algorithm designed to improve on bubble sort. It keeps the familiar process of comparing neighbouring values, but begins with items separated by a larger gap. As the gap shrinks, the algorithm gradually changes from broad rearrangement to a final bubble-sort-style pass.

This approach is useful for learning how a small change in comparison distance can affect performance. It also gives programmers a compact in-place sorting method for modest datasets, especially when implementation simplicity matters more than guaranteed fast asymptotic performance.

What comb sort changes about bubble sort

Bubble sort compares adjacent elements, so a very small value near the end of an array may move towards the front only one position per pass. This is sometimes described as a “turtle” problem: a slow-moving small item can force many unnecessary comparisons.

Comb sort addresses this by comparing elements separated by a gap. For an array containing 20 values, an early pass might compare positions 0 and 15, then 1 and 16, and so on. A small value can move a long distance in a single swap. Later passes use smaller gaps, allowing the algorithm to refine the order.

The method still uses a comparison such as a[i] > a[i + gap]. If the earlier value is larger, the two values are exchanged. The process continues until the gap is one and a complete pass makes no swaps. That final condition is important: having a gap of one does not automatically mean the array is sorted.

Comb sort is usually not stable, meaning equal values may change their original relative order. It is, however, in-place because it needs only a constant amount of additional memory for variables and temporary swap storage.

Understanding the gap sequence

The gap sequence is the defining feature of this algorithm. A typical implementation starts with the array length and divides the gap by a shrink factor, commonly 1.3. The result is rounded down to an integer, with a minimum gap of one.

For example, an array of length 30 might produce a sequence similar to 30, 23, 17, 13, 10, 7, 5, 3, 2, and 1. Each pass compares values that are that many positions apart. The exact sequence varies with the input length, but the principle remains the same: begin with long-distance comparisons and finish with local comparisons.

The factor 1.3 is a practical compromise rather than a mathematical law. A factor close to 1 shrinks the gap slowly, creating many passes. A much larger factor shrinks it too quickly and may leave disorder for the final gap-one passes. Researchers and programmers have tested alternative sequences, but 1.3 remains common because it is easy to implement and performs reasonably well.

A popular variant, often called comb sort 11, modifies the sequence when the calculated gap is 9 or 10. It replaces either value with 11. This small adjustment is intended to avoid less effective gap patterns observed in testing. The special case does not change the algorithm’s structure, but it can improve practical results on some inputs.

The final gap must always be one. The loop must also continue when the gap has reached one if a swap occurred during the last pass. Otherwise, an inversion created or left behind during that pass could be missed. The stopping condition is therefore usually expressed as “gap equals one and no swaps occurred”.

A worked example and pseudocode

Consider the values [8, 3, 7, 1, 6, 2, 5, 4]. Bubble sort initially compares 8 with 3, then 7 with 1, and so forth. Comb sort might begin with a gap of six, comparing 8 with 5 and 3 with 4. These distant comparisons can move values towards their approximate final regions before the algorithm begins its fine-grained work.

Suppose the next gap is four. The algorithm compares positions 0 and 4, 1 and 5, 2 and 6, and 3 and 7. It then reduces the gap again and repeats the scan. At gap one, it behaves like bubble sort, but the earlier passes have already removed many long-distance inversions.

The core procedure can be represented with the following pseudocode:

comb_sort(array):
    gap = length(array)
    swapped = true

    while gap != 1 or swapped == true:
        gap = floor(gap / 1.3)

        if gap < 1:
            gap = 1

        if gap == 9 or gap == 10:
            gap = 11

        swapped = false

        for i from 0 while i + gap < length(array):
            if array[i] > array[i + gap]:
                swap array[i] and array[i + gap]
                swapped = true

    return array

The swapped flag prevents unnecessary repeated scans after the data is ordered. Notice that the outer loop uses an OR condition. When the gap is greater than one, another pass is required even if the previous pass made no swaps, because a later smaller gap may reveal comparisons that have not yet been made.

Python implementation and complexity

A direct Python implementation follows the pseudocode closely:

def comb_sort(values):
    gap = len(values)
    swapped = True

    while gap != 1 or swapped:
        gap = int(gap / 1.3)

        if gap < 1:
            gap = 1
        if gap in (9, 10):
            gap = 11

        swapped = False

        for i in range(len(values) - gap):
            j = i + gap
            if values[i] > values[j]:
                values[i], values[j] = values[j], values[i]
                swapped = True

    return values

This function sorts the existing list and returns the same list object. The range expression is safe because the largest valid left-hand index is len(values) - gap - 1. Empty and one-element lists also work: the initial gap is reduced to one, and the loop finishes without attempting an invalid comparison.

The worst-case time complexity is generally given as O(n²), while auxiliary space complexity is O(1). The best case can be close to O(n log n) for some gap sequences and inputs, although practical descriptions often avoid promising a strict best-case bound because the number of passes depends on the sequence and implementation. Comb sort has no universal O(n log n) guarantee like merge sort or heap sort.

Its practical performance is often better than bubble sort because large gaps remove disorder quickly. It still tends to lose to well-engineered quicksort, heapsort, Timsort, or the sorting functions provided by a programming language. The algorithm is therefore valuable for education, constrained environments, and small utilities rather than as a default replacement for Python’s sort().

It is also useful to compare its design with algorithms that solve a different kind of problem. For example, the dynamic programming approach for longest common subsequence addresses optimal relationships between sequences, whereas comb sort simply rearranges elements according to a comparison rule. Knowing the complexity model and output requirements prevents choosing a sorting method for a problem that is not actually a sorting problem.

When the algorithm makes sense

Comb sort suits situations where a compact implementation, low memory use, and understandable mechanics are more important than predictable high performance. It can be a useful exercise in a university or TAFE programming class, where students can measure how different gap factors affect the number of comparisons and swaps.

It may also appear in small embedded or educational programs where allocating a second array is undesirable. A developer working with a modest data buffer on a remote Australian installation, for example, might appreciate an in-place algorithm that is easy to inspect. For production software handling large records, however, the standard library’s tested sort is normally the safer choice.

Australian developers often work across broad distances, from teams in Sydney and Melbourne to offices in Perth, Darwin, or regional Queensland. Network latency over an NBN connection can make remote data access noticeable, but it does not make a poor local sorting algorithm efficient; transferring less data is usually more valuable than replacing a library sort with comb sort. In a coding interview or a quick “arvo” prototype, explaining the gap sequence may be more important than claiming it is the fastest option.

The algorithm can be benchmarked with random, nearly sorted, reversed, and duplicate-heavy arrays. Measurements should include elapsed time, comparisons, swaps, and input size. Results can differ between a laptop in Brisbane and a cloud instance in an Australian region because processor generation, Python version, and workload matter more than geography itself.

Comb sort also provides a useful contrast with optimisation algorithms. A simplex algorithm guide concerns linear programming and feasible solutions, not ordering values in an array. Both topics demonstrate why algorithm selection begins with the structure of the problem. For sorting, the gap sequence controls how disorder is reduced; for linear programming, constraints and an objective function control the search.

Used with those limitations in mind, comb sort is a clear example of algorithmic refinement. It keeps the approachable mechanics of bubble sort, adds long-distance comparisons through a shrinking gap, and finishes with a reliable gap-one pass. That combination makes it a practical teaching tool and a memorable part of the family of comparison-based sorting algorithms.