Comb Sort: Improved Bubble Sort Variant
Bubble sort has earned its reputation as the algorithm you learn first and abandon immediately. Its O(n²) time complexity isn't the only issue—the real killer is what's known as the 'turtle problem.'
Key Insights
- Comb sort eliminates bubble sort’s “turtle problem” by comparing elements across gaps rather than adjacent positions, dramatically improving average-case performance from O(n²) to O(n log n)
- The shrink factor of 1.3 isn’t arbitrary—it’s empirically proven to provide optimal gap sequences that balance comparison efficiency with convergence speed
- While comb sort rarely appears in production code, understanding it bridges the conceptual gap between simple quadratic sorts and sophisticated algorithms like Shell sort
The Problem with Bubble Sort
Bubble sort has earned its reputation as the algorithm you learn first and abandon immediately. Its O(n²) time complexity isn’t the only issue—the real killer is what’s known as the “turtle problem.”
Consider an array where small values sit near the end. In bubble sort, these values can only move one position per pass through the array. A value that needs to travel from position n-1 to position 0 requires n-1 complete passes. Meanwhile, large values at the beginning (“rabbits”) quickly bubble to their correct positions.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
# The turtle problem in action
# Array: [2, 3, 4, 5, 1]
# The '1' must bubble left one position per pass
# Requires 4 complete passes just for this one element
Comb sort attacks this asymmetry directly. Instead of comparing adjacent elements, it compares elements separated by a gap. This allows turtles to leap toward their destinations rather than crawl.
The Comb Sort Algorithm Explained
Comb sort, developed by Włodzimierz Dobosiewicz in 1980 and later rediscovered by Stephen Lacey and Richard Box in 1991, introduces a simple but powerful modification to bubble sort: variable-width gaps.
The algorithm starts with a large gap (typically the array length divided by 1.3) and makes passes through the array comparing elements at that distance. After each pass, the gap shrinks by the same factor until it reaches 1. At gap=1, comb sort behaves exactly like bubble sort, but by then, most elements are already close to their final positions.
def comb_sort(arr):
n = len(arr)
gap = n
shrink_factor = 1.3
sorted = False
while not sorted:
# Calculate next gap
gap = int(gap / shrink_factor)
if gap <= 1:
gap = 1
sorted = True # Will become False if we swap
# Compare elements at current gap
i = 0
while i + gap < n:
if arr[i] > arr[i + gap]:
arr[i], arr[i + gap] = arr[i + gap], arr[i]
sorted = False
i += 1
return arr
function combSort(arr) {
const n = arr.length;
let gap = n;
const shrinkFactor = 1.3;
let sorted = false;
while (!sorted) {
gap = Math.floor(gap / shrinkFactor);
if (gap <= 1) {
gap = 1;
sorted = true;
}
for (let i = 0; i + gap < n; i++) {
if (arr[i] > arr[i + gap]) {
[arr[i], arr[i + gap]] = [arr[i + gap], arr[i]];
sorted = false;
}
}
}
return arr;
}
The algorithm terminates when a complete pass with gap=1 produces no swaps, indicating the array is sorted.
Gap Sequence: The Key Innovation
The gap sequence is where comb sort’s magic happens. Starting from the array length, each subsequent gap is calculated by dividing the previous gap by the shrink factor.
For an array of 100 elements with shrink factor 1.3:
- Pass 1: gap = 76
- Pass 2: gap = 58
- Pass 3: gap = 44
- Pass 4: gap = 34
- Pass 5: gap = 26
- Pass 6: gap = 20
- Pass 7: gap = 15
- Pass 8: gap = 11
- Pass 9: gap = 8
- Pass 10: gap = 6
- Pass 11: gap = 4
- Pass 12: gap = 3
- Pass 13: gap = 2
- Pass 14: gap = 1
def visualize_gap_sequence(n, shrink_factor=1.3):
"""Generate and display the gap sequence for an array of size n."""
gaps = []
gap = n
while gap > 1:
gap = int(gap / shrink_factor)
if gap < 1:
gap = 1
gaps.append(gap)
print(f"Array size: {n}")
print(f"Shrink factor: {shrink_factor}")
print(f"Number of gap values: {len(gaps)}")
print(f"Gap sequence: {gaps}")
return gaps
# Example output for n=1000:
# Array size: 1000
# Shrink factor: 1.3
# Number of gap values: 24
# Gap sequence: [769, 591, 454, 349, 268, 206, 158, 121, 93, 71,
# 54, 41, 31, 23, 17, 13, 10, 7, 5, 3, 2, 1, 1, 1]
Why 1.3? Lacey and Box tested various shrink factors empirically and found that 1.3 produces the best average-case performance. Values too close to 1.0 create too many passes; values too large skip over elements that need comparison.
This approach shares DNA with Shell sort, which also uses gap sequences. However, Shell sort’s gap sequences are typically more complex (Hibbard’s, Sedgewick’s, or Tokuda’s sequences), while comb sort’s geometric progression is simpler to implement and remember.
Performance Analysis
Comb sort’s performance characteristics make it genuinely useful in specific contexts:
- Worst case: O(n²) — still possible with pathological inputs
- Average case: O(n log n) — a massive improvement over bubble sort
- Best case: O(n log n) — when the array is already nearly sorted
- Space complexity: O(1) — sorts in place with no additional memory
import time
import random
def benchmark_sorts(sizes):
"""Compare bubble sort and comb sort performance."""
results = []
for size in sizes:
# Generate random array
original = [random.randint(0, 10000) for _ in range(size)]
# Benchmark bubble sort
arr = original.copy()
start = time.perf_counter()
bubble_sort(arr)
bubble_time = time.perf_counter() - start
# Benchmark comb sort
arr = original.copy()
start = time.perf_counter()
comb_sort(arr)
comb_time = time.perf_counter() - start
speedup = bubble_time / comb_time if comb_time > 0 else float('inf')
results.append({
'size': size,
'bubble_sort': f"{bubble_time:.4f}s",
'comb_sort': f"{comb_time:.4f}s",
'speedup': f"{speedup:.1f}x"
})
return results
# Typical results:
# Size 1000: Bubble: 0.0892s, Comb: 0.0021s, Speedup: 42.5x
# Size 5000: Bubble: 2.2341s, Comb: 0.0134s, Speedup: 166.7x
# Size 10000: Bubble: 8.9123s, Comb: 0.0298s, Speedup: 299.1x
The speedup becomes more dramatic as array size increases—exactly what you’d expect when comparing O(n²) to O(n log n) average-case behavior.
Optimizations and Variants
The most well-known optimization is Combsort11, which addresses a subtle issue with the standard algorithm. When the gap sequence produces values of 9 or 10, the algorithm can get stuck in certain patterns. Combsort11 forces these gaps to 11 instead.
def comb_sort_11(arr):
"""Optimized comb sort with the '11' rule."""
n = len(arr)
gap = n
shrink_factor = 1.3
sorted = False
while not sorted:
gap = int(gap / shrink_factor)
# The "11" optimization
if gap == 9 or gap == 10:
gap = 11
if gap <= 1:
gap = 1
sorted = True
i = 0
while i + gap < n:
if arr[i] > arr[i + gap]:
arr[i], arr[i + gap] = arr[i + gap], arr[i]
sorted = False
i += 1
return arr
def hybrid_comb_insertion_sort(arr, insertion_threshold=10):
"""Comb sort with insertion sort finish for small gaps."""
n = len(arr)
gap = n
shrink_factor = 1.3
# Comb sort phase
while gap > insertion_threshold:
gap = int(gap / shrink_factor)
for i in range(n - gap):
if arr[i] > arr[i + gap]:
arr[i], arr[i + gap] = arr[i + gap], arr[i]
# Insertion sort finish
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
The hybrid approach recognizes that once elements are mostly sorted, insertion sort’s low overhead makes it faster than continuing with comb sort’s gap comparisons.
Practical Applications and Trade-offs
Should you use comb sort in production? Probably not. Standard library sort functions use highly optimized algorithms like Timsort or introsort that outperform comb sort in virtually all scenarios.
However, comb sort has legitimate use cases:
Memory-constrained embedded systems: When you can’t afford the O(n) auxiliary space of merge sort and need better average performance than insertion sort, comb sort’s O(1) space and O(n log n) average case make it attractive.
Educational contexts: Comb sort perfectly illustrates how a simple modification to a naive algorithm can yield dramatic improvements. It’s an excellent stepping stone to understanding Shell sort and the importance of gap sequences.
Quick implementations: When you need a reasonably fast sort and can’t use library functions (competitive programming, coding interviews, or scripting in limited environments), comb sort is easy to implement correctly from memory.
The trade-offs are clear: you get simplicity and low memory usage at the cost of worst-case guarantees and raw speed compared to more sophisticated algorithms.
Conclusion
Comb sort transforms bubble sort from a pedagogical curiosity into a genuinely useful algorithm. By introducing gap sequences, it eliminates the turtle problem that makes bubble sort impractical for anything beyond trivially small arrays.
The key takeaways: the 1.3 shrink factor provides empirically optimal gap sequences, the algorithm achieves O(n log n) average-case performance while maintaining O(1) space complexity, and the Combsort11 variant handles edge cases that can slow down the basic implementation.
In the sorting algorithm landscape, comb sort occupies a specific niche: simpler than Shell sort, faster than bubble sort, and more memory-efficient than merge sort. It won’t replace your language’s built-in sort, but understanding it deepens your appreciation for how algorithmic improvements compound into real-world performance gains.