Comb Sort

Comb Sort is an improved version of Bubble Sort that eliminates "turtles" (small values near the end of the array) by using a gap larger than 1. It starts with a large gap and shrinks it using a shrink factor until the gap becomes 1, at which point it becomes a standard Bubble Sort.

Complexity Analysis

Best Case

O(n log n)

Average Case

O(n²/2^p)

Worst Case

O(n²)

Space Complexity

O(1)

function combSort(arr) {
    const n = arr.length;
    const shrink = 1.3; // Shrink factor
    let gap = n;

    let sorted = false;

    while (!sorted) {
        // Update gap using shrink factor
        gap = Math.floor(gap / shrink);

        // Minimum gap is 1
        if (gap <= 1) {
            gap = 1;
            sorted = true;
        }

        // Compare elements with current gap
        for (let i = 0; i < n - gap; i++) {
            if (arr[i] > arr[i + gap]) {
                // Swap elements
                [arr[i], arr[i + gap]] = [arr[i + gap], arr[i]];
                sorted = false; // Array was not sorted
            }
        }
    }

    return arr;
}

How Comb Sort Works

Comb Sort improves Bubble Sort by eliminating turtles (small values that move slowly through the array). It uses a gap larger than 1 and shrinks it progressively, allowing large values to move quickly to their correct positions.

Algorithm Steps:

  1. Initialize Gap: Start with gap = array length
  2. Shrink Gap: Divide gap by shrink factor (typically 1.3)
  3. Compare with Gap: Compare elements that are gap positions apart
  4. Swap if Needed: Exchange elements if out of order
  5. Continue: Repeat until gap becomes 1
  6. Final Pass: Standard bubble sort when gap = 1

Comb Sort vs Bubble Sort:

  • Larger jumps: Compares elements far apart initially
  • Turtle elimination: Small elements near end move quickly
  • Fewer comparisons: Generally more efficient than bubble sort
  • Same simplicity: Easy to understand and implement

Key Characteristics:

  • In-place: Requires only constant extra space O(1)
  • Unstable: Does not maintain relative order of equal elements
  • Adaptive: Performance improves with partially sorted data
  • Simple: Based on familiar bubble sort with gap concept

Shrink Factor:

  • 1.3: Most commonly used shrink factor
  • Optimal value: Balances gap reduction with performance
  • Mathematical basis: Related to golden ratio properties
  • Performance impact: Different factors affect convergence rate

Performance Insights:

  • Best Case: O(n log n) for nearly sorted arrays
  • Average Case: O(n²/2^p) where p relates to shrink factor
  • Worst Case: O(n²) for certain pathological inputs
  • Improvement: Usually 3-5x faster than bubble sort

Historical Context:

  • Invented: 1980 by Włodzimierz Dobosiewicz
  • Popularized: Later by Stephen Lacey and Richard Box
  • Inspiration: Based on Shell sort concepts
  • Practical use: Used in some embedded systems and educational contexts

When to Use Comb Sort:

  • Educational purposes: Demonstrates gap-based sorting improvements
  • Simple implementation needed: When bubble sort needs performance boost
  • Memory constrained: When additional space isn't available
  • Understanding sorting: Bridge between bubble sort and more advanced algorithms