Overview & Concept
Comb Sort is a significant enhancement over Bubble Sort designed by Włodzimierz Dobosiewicz in 1980 and popularized by Stephen Lacey and Richard Box. By using a shrink factor of 1.3 to reduce the comparison gap on each pass, Comb Sort rapidly moves small values located near the end of the array ("turtles") toward the front.
How It Works
Large Initial Gap: Initializes gap = floor(n / 1.3), comparing elements widely separated across the array.
Turtle Elimination: Swapping widely separated elements moves small values near the tail directly toward the head in single operations.
Shrink Factor 1.3: Decreases the gap by dividing by 1.3 after each iteration, which empirically eliminates inversions most efficiently.
Comb Sort 11 Rule: If the gap calculates to 9 or 10, it is rounded up to 11 to eliminate turtle clusters before the final gap-1 passes.
Step-by-Step Execution
Asymptotic Complexity Analysis
| Metric | Best Case | Average Case | Worst Case | Space Complexity |
|---|---|---|---|---|
| Complexity Bound | O(n log n) | O(n log n) | O(n²) | O(1) |
| Explanation | Optimal input arrangement minimizing operations. | Expected time for uniformly distributed randomized inputs. | Adversarial degenerate conditions requiring full traversal. | Auxiliary memory allocated beyond original input size. |
Pseudocode & Invariants
procedure combSort(A):
gap = length(A); shrink = 1.3; swapped = true
while gap > 1 or swapped:
gap = floor(gap / shrink)
if gap < 1: gap = 1
if gap == 9 or gap == 10: gap = 11
swapped = false
for i = 0 to n - gap - 1:
if A[i] > A[i + gap]: swap(A[i], A[i + gap]); swapped = true
return A- Gap Monotonicity: Gap shrinks strictly monotonically toward 1 on each pass.
Advantages & Disadvantages
Key Advantages
- •Dramatic performance improvement over Bubble Sort (O(n log n) average vs O(n²)).
- •In-place sort requiring O(1) auxiliary space.
- •Simple implementation with minimal constant memory overhead.
Trade-offs & Limitations
- •Unstable: large gap swaps can alter relative order of duplicate elements.
- •Worst-case performance is still O(n²) on specific adversarial inputs.
Real-World Applications
Graphic Subsystems & CAD
Simple low-memory rendering pipelines where microcode simplicity is vital.
Hardware Microcontrollers
Embedded microprocessors with limited flash memory incapable of storing recursive quicksort routines.
Decision Guide: When to Use
Ideal Scenarios
- ✓When an in-place, non-recursive sort faster than Bubble Sort or Insertion Sort is desired.
Consider Alternatives When
- ✕When stable sorting is required or input size exceeds millions of elements.
Explore Related Algorithms
Compare trade-offs and complexity across complementary tools in AlgoViz.