Comb Sort

Comb sort improves bubble sort by comparing elements that are far apart before comparing adjacent elements. It starts with a large gap and repeatedly shrinks that gap until it reaches 1.

The main idea is to remove small elements near the end and large elements near the beginning earlier than bubble sort would.

Problem

Given a sequence $A$ of length $n$ , reorder it such that

A[0] \le A[1] \le \cdots \le A[n-1]

Algorithm

Start with gap $n$ . Divide the gap by a shrink factor, commonly about $1.3$ , until the gap becomes 1. Keep scanning while swaps still occur.

comb_sort(A):
    n = length(A)
    gap = n
    shrink = 1.3
    sorted = false

    while sorted == false:
        gap = floor(gap / shrink)
        if gap <= 1:
            gap = 1
            sorted = true

        i = 0
        while i + gap < n:
            if A[i] > A[i + gap]:
                swap(A[i], A[i + gap])
                sorted = false
            i = i + 1

Example

Let

A = [8, 4, 1, 56, 3, 44, 23, 6]

Early passes use large gaps, so values can move long distances:

gap	effect
6	compares far-apart elements
4	moves misplaced elements closer
3	reduces medium-distance inversions
2	nearly orders the array
1	finishes like bubble sort

Final result:

[1, 3, 4, 6, 8, 23, 44, 56]

Correctness

Comb sort repeatedly swaps out-of-order pairs at decreasing gaps. When the gap becomes 1, the algorithm performs adjacent comparisons like bubble sort. It continues until a full gap-1 pass completes without swaps, which means every adjacent pair is ordered. Therefore the entire sequence is sorted.

Complexity

case	time
best	$O(n \log n)$
worst	$O(n^2)$
average	often better than bubble sort

Space complexity:

O(1)

Properties

in-place
not stable
simple gap-based improvement over bubble sort
depends on shrink factor

When to Use

Comb sort is useful as a simple improvement over bubble sort when implementation must remain small. It is mainly educational, but it shows how gap-based comparisons can remove long-distance inversions before the final adjacent pass.

Implementation

def comb_sort(a):
    n = len(a)
    gap = n
    shrink = 1.3
    sorted_flag = False

    while not sorted_flag:
        gap = int(gap / shrink)
        if gap <= 1:
            gap = 1
            sorted_flag = True

        i = 0
        while i + gap < n:
            if a[i] > a[i + gap]:
                a[i], a[i + gap] = a[i + gap], a[i]
                sorted_flag = False
            i += 1

    return a

func CombSort[T constraints.Ordered](a []T) {
    n := len(a)
    gap := n
    shrink := 1.3
    sorted := false

    for !sorted {
        gap = int(float64(gap) / shrink)
        if gap <= 1 {
            gap = 1
            sorted = true
        }

        for i := 0; i+gap < n; i++ {
            if a[i] > a[i+gap] {
                a[i], a[i+gap] = a[i+gap], a[i]
                sorted = false
            }
        }
    }
}