How Comb Sort Works: Step-by-Step Guide

Introduction and Core Concepts

Comb Sort is a relatively simple yet surprisingly effective sorting algorithm that improves upon the classic Bubble Sort by eliminating one of its most significant weaknesses: the slow movement of small values trapped at the end of the array, often called "turtles." Invented by Stephen Lacey and Richard Box in 1980 and later popularized by its detailed description in Byte Magazine in April 1991, Comb Sort introduces the concept of a gap that starts large and shrinks over time, allowing elements to make long-distance jumps early in the process.

At its core, Comb Sort belongs to the family of comparison-based, in-place sorting algorithms. Like Bubble Sort, it repeatedly compares pairs of elements and swaps them if they are out of order. The critical difference is that Comb Sort does not limit comparisons to adjacent neighbors. Instead, it compares elements separated by a gap, which is initially set to the length of the array and then progressively reduced by a shrink factor, typically 1.3. This mechanism allows the algorithm to quickly move misplaced elements to their approximate correct region before fine-tuning with smaller gaps.

Why does Comb Sort matter in the modern landscape of sorting algorithms? While it is not the fastest general-purpose sort for large datasets — algorithms like Quicksort, Mergesort, and Timsort dominate production libraries — Comb Sort holds significant educational and practical value. It demonstrates how a single conceptual tweak can transform an O(n²) algorithm into one with an average-case performance of O(n²/2^p) or empirically around O(n log n) in many cases, while retaining the simplicity and minimal memory overhead of Bubble Sort. For embedded systems, small datasets, or environments where code simplicity and low memory usage are critical, Comb Sort remains a compelling choice.

What Defines Comb Sort?

Comb Sort can be defined by three core characteristics. First, it is an in-place algorithm, meaning it requires only O(1) auxiliary space beyond the input array. Second, it is unstable in its basic form, as distant swaps can change the relative order of equal elements. Third, it is not adaptive in the strictest sense, but its performance does benefit from partially sorted data because the final pass with a gap of 1 acts like an optimized Bubble Sort that can terminate early if no swaps occur.

The name "Comb" itself is a visual metaphor. Think of the array as hair and the gap as the teeth of a comb. The algorithm combs through the array with wide teeth first, detangling large knots, and then uses progressively finer teeth to smooth out the remaining disorder. This intuitive analogy makes it one of the easiest improved sorting algorithms to understand and implement.

How It Works

The mechanism of Comb Sort is best understood as a generalization of Bubble Sort. Bubble Sort only compares and swaps adjacent elements (gap = 1), which means an element that belongs at the beginning of the array but is currently at the end must bubble forward one position at a time, requiring n steps. Comb Sort solves this by starting with a large gap, allowing that element to leap forward much faster.

The algorithm proceeds in phases. It begins by calculating an initial gap, usually the length of the array n. It then enters a loop where it iterates through the array, comparing the element at index i with the element at index i + gap. If the two are out of order (for ascending sort, if arr[i] > arr[i + gap]), they are swapped. After completing one full pass across the array with the current gap, the gap is reduced by dividing it by the shrink factor (commonly 1.3) and truncating to an integer. The process repeats until the gap is 1 and a complete pass is made with no swaps, indicating the array is sorted.

The choice of the shrink factor is crucial and has been the subject of empirical research. A value that is too large (e.g., 2.0) causes the gap to shrink too quickly, missing opportunities for efficient long-distance swaps. A value too small (e.g., 1.1) causes many passes with similar gap sizes, wasting comparisons. Extensive testing by Lacey and Box and later researchers showed that 1.3 is the optimal sweet spot, yielding the best average performance across random datasets. This value balances the number of passes against the effectiveness of each pass.

The Role of the Shrink Factor

Mathematically, the shrink factor determines the sequence of gaps. For an array of size n, the gap sequence will be: n, n/1.3, n/1.3², n/1.3³, ... until it reaches 1. For example, with n=10, the gaps would be 10, 7, 5, 3, 2, 1. Each gap size defines a set of interleaved subarrays. When gap=5, you are effectively sorting 5 interleaved subarrays (indices 0,5; 1,6; 2,7; etc.) in a single pass. This is conceptually similar to Shell Sort, but Shell Sort uses a different gap sequence and insertion sort for each subarray, while Comb Sort uses a simple swap-based comparison.

The termination condition is also important. The algorithm does not stop simply when the gap becomes 1. It must perform one final bubble-sort-like pass with gap=1 and verify that no swaps were needed. If swaps did occur during the gap=1 pass, it means the array was not yet fully sorted, and another gap=1 pass is required. This is typically implemented with a boolean flag such as `swapped` or `sorted`.

Why It Eliminates Turtles

In Bubble Sort, "rabbits" (large values at the beginning) move quickly because they are swapped forward repeatedly in a single pass. "Turtles" (small values at the end) move slowly because they can only move backward by one position per pass. Comb Sort's large initial gap directly addresses turtles. A small value at the end of the array will be compared with an element near the beginning in the first few passes and can be swapped forward by a large distance immediately. By the time the gap shrinks to 1, most turtles have already been relocated, leaving only a nearly-sorted array for the final adjacent comparisons to clean up.

Implementation

Implementing Comb Sort in Python is straightforward and requires only a few lines of code beyond a standard Bubble Sort. The key is to correctly manage the gap calculation, the loop termination, and the swap logic. Below are several implementations that illustrate the core algorithm and its practical nuances.

Basic Comb Sort Implementation

This first implementation is the canonical version using the empirically optimal shrink factor of 1.3. It sorts the array in place and returns the same array for convenience.

def comb_sort(arr):
    """
    Basic Comb Sort implementation.
    Sorts the list in-place in ascending order.
    """
    n = len(arr)
    gap = n
    shrink = 1.3
    sorted_flag = False

    while not sorted_flag:
        # Update the gap for next iteration
        gap = int(gap / shrink)
        if gap <= 1:
            gap = 1
            sorted_flag = True  # Assume sorted, will be falsified if swap occurs

        i = 0
        while i + gap < n:
            if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                sorted_flag = False  # Swap means array was not sorted
            i += 1

    return arr

# Example usage
data = [8, 4, 1, 56, 12, -5, 2, 0]
print(comb_sort(data))  # Output: [-5, 0, 1, 2, 4, 8, 12, 56]

This code highlights the two nested loops: the outer `while not sorted_flag` loop controls the gap reduction, and the inner `while i + gap < n` loop performs the comparisons for a given gap. The `sorted_flag` is only set to True when the gap is 1, and it is immediately set back to False if any swap occurs, forcing another pass.

Comb Sort with Detailed Gap Tracking

For debugging and educational purposes, it is helpful to instrument the algorithm to observe how the gap evolves and how many comparisons and swaps occur per pass.

def comb_sort_verbose(arr):
    """Comb Sort that prints gap and swap information for each pass."""
    n = len(arr)
    gap = n
    shrink = 1.3
    sorted_flag = False
    pass_num = 0

    print(f"Initial array: {arr}")
    while not sorted_flag:
        gap = int(gap / shrink)
        if gap <= 1:
            gap = 1
            sorted_flag = True

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

        print(f"Pass {pass_num}: gap={gap}, swaps={swaps_this_pass}, array={arr}")
        # Prevent infinite loop for gap=1 with no swaps
        if gap == 1 and swaps_this_pass == 0:
            break

    return arr

# verbose_data = [5, 1, 4, 2, 8, 0, 2]
# comb_sort_verbose(verbose_data)

Generic Comb Sort with Custom Comparator

A more flexible implementation allows sorting in descending order or sorting complex objects by accepting a key function or comparator, similar to Python's built-in `sort`.

def comb_sort_generic(arr, reverse=False, key=None):
    """
    Generic Comb Sort supporting reverse and key functions.
    """
    n = len(arr)
    gap = n
    shrink = 1.3
    sorted_flag = False

    # Helper to get comparison value
    def get_val(x):
        return key(x) if key else x

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

        i = 0
        while i + gap < n:
            a_val = get_val(arr[i])
            b_val = get_val(arr[i + gap])
            # Determine if swap is needed
            should_swap = a_val > b_val if not reverse else a_val < b_val
            if should_swap:
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                sorted_flag = False
            i += 1
    return arr

# Sort list of tuples by second element
pairs = [(1, 3), (2, 1), (5, 2)]
comb_sort_generic(pairs, key=lambda x: x[1])
print(pairs)  # [(2, 1), (5, 2), (1, 3)]

# Descending sort
nums = [3, 1, 4, 1, 5]
comb_sort_generic(nums, reverse=True)
print(nums)  # [5, 4, 3, 1, 1]

Optimized Comb Sort 11 Variant

The most well-known optimization is Comb Sort 11, which tweaks the gap sequence to avoid gaps of 9 and 10, which were found to be less effective. If the gap becomes 9 or 10, it is forced to 11. This small change improves performance on certain data distributions.

def comb_sort_11(arr):
    """
    Comb Sort 11 optimization: if gap becomes 9 or 10, set it to 11.
    This variant is considered the standard optimized version.
    """
    n = len(arr)
    gap = n
    shrink = 1.3
    sorted_flag = False

    while not sorted_flag:
        gap = int(gap / shrink)
        # Comb Sort 11 rule
        if gap == 9 or gap == 10:
            gap = 11

        if gap <= 1:
            gap = 1
            sorted_flag = True

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

    return arr

# Test on array where gap 9/10 would occur
test_arr = list(range(20, 0, -1))
print(comb_sort_11(test_arr.copy()))

Step-by-Step Example

To solidify understanding, let us walk through Comb Sort on a concrete array: [8, 4, 1, 56, 12, -5, 2, 0] with n=8 and shrink factor 1.3. We will trace the gap, the comparisons, and the array state after each pass.

Initial State: arr = [8, 4, 1, 56, 12, -5, 2, 0], gap = 8

Pass 1: gap = int(8 / 1.3) = 6
We compare elements 6 apart:
Compare arr[0]=8 and arr[6]=2 → 8 > 2, swap → [2, 4, 1, 56, 12, -5, 8, 0]
Compare arr[1]=4 and arr[7]=0 → 4 > 0, swap → [2, 0, 1, 56, 12, -5, 8, 4]
End of pass 1. Array is now [2, 0, 1, 56, 12, -5, 8, 4]. Notice how the large values 8 and 4 have moved significantly from the front to the end.

Pass 2: gap = int(6 / 1.3) = 4
Compare arr[0]=2 and arr[4]=12 → 2 < 12, no swap
Compare arr[1]=0 and arr[5]=-5 → 0 > -5, swap → [2, -5, 1, 56, 12, 0, 8, 4]
Compare arr[2]=1 and arr[6]=8 → 1 < 8, no swap
Compare arr[3]=56 and arr[7]=4 → 56 > 4, swap → [2, -5, 1, 4, 12, 0, 8, 56]
End of pass 2. Array: [2, -5, 1, 4, 12, 0, 8, 56]. The smallest value -5 is now moving toward the front.

Pass 3: gap = int(4 / 1.3) = 3
Compare arr[0]=2 and arr[3]=4 → no swap
Compare arr[1]=-5 and arr[4]=12 → no swap
Compare arr[2]=1 and arr[5]=0 → 1 > 0, swap → [2, -5, 0, 4, 12, 1, 8, 56]
Compare arr[3]=4 and arr[6]=8 → no swap
Compare arr[4]=12 and arr[7]=56 → no swap
End of pass 3. Array: [2, -5, 0, 4, 12, 1, 8, 56]

Pass 4: gap = int(3 / 1.3) = 2
Compare arr[0]=2 and arr[2]=0 → swap → [-5? Wait: 2 > 0 swap → [0, -5, 2, 4, 12, 1, 8, 56]]
Compare arr[1]=-5 and arr[3]=4 → no swap → [0, -5, 2, 4, 12, 1, 8, 56]
Compare arr[2]=2 and arr[4]=12 → no swap
Compare arr[3]=4 and arr[5]=1 → swap → [0, -5, 2, 1, 12, 4, 8, 56]
Compare arr[4]=12 and arr[6]=8 → swap → [0, -5, 2, 1, 8, 4, 12, 56]
Compare arr[5]=4 and arr[7]=56 → no swap
End of pass 4. Array: [0, -5, 2, 1, 8, 4, 12, 56]

Pass 5: gap = int(2 / 1.3) = 1
This is the final bubble-sort phase. The algorithm will now perform adjacent comparisons until no swaps occur.
First gap=1 pass:
0 vs -5 → swap → [-5, 0, 2, 1, 8, 4, 12, 56]
0 vs 2 → no swap
2 vs 1 → swap → [-5, 0, 1, 2, 8, 4, 12, 56]
2 vs 8 → no swap
8 vs 4 → swap → [-5, 0, 1, 2, 4, 8, 12, 56]
8 vs 12 → no swap
12 vs 56 → no swap
Since swaps occurred, sorted_flag is set to False, so another gap=1 pass is required.

Pass 6: gap = 1 (again)
Compare all adjacent pairs: [-5,0], [0,1], [1,2], [2,4], [4,8], [8,12], [12,56] — no swaps occur. The sorted_flag remains True, and the algorithm terminates. Final sorted array: [-5, 0, 1, 2, 4, 8, 12, 56].

This walkthrough illustrates how early large gaps quickly repositioned distant elements, leaving only minor local inversions for the final gap=1 passes to resolve. Without the large gaps, the -5 at index 5 would have required 5 separate adjacent swaps to reach index 0.

Complexity Analysis

Analyzing Comb Sort's complexity is more nuanced than for many other algorithms because its performance depends heavily on the shrink factor and the data distribution. Unlike algorithms with tight theoretical bounds, much of Comb Sort's analysis is empirical.

In the worst case, Comb Sort still degrades to O(n²). This occurs with certain pathological inputs where the gap sequence fails to sufficiently disorder the array before the final bubble sort phase. However, this worst case is far rarer than in Bubble Sort. The average-case complexity is widely cited as O(n²/2^p), where p is the number of increments, but more practically it is often described as O(n log n) for random data. This is a dramatic improvement over Bubble Sort's O(n²) average case.

The best case occurs when the array is already sorted. In this scenario, the algorithm will still iterate through all gap values, performing n - gap comparisons for each gap, but will never swap. The final gap=1 pass will confirm that no swaps are needed and terminate. The total number of comparisons is the sum of (n - gap) for each gap in the sequence, which is approximately O(n log n) due to the logarithmic number of gaps. Some optimized implementations add an early-exit check to detect a sorted array faster, but the standard version does not achieve O(n) best case like Insertion Sort.

Space complexity is a clear strength: O(1) auxiliary space. The sort is performed in place, requiring only a few integer variables (gap, i, shrink factor) and a boolean flag, regardless of input size.

Understanding the Empirical O(n log n) Claim

It is important to note that the O(n log n) average case is not a proven tight bound like that of Mergesort. It is an observed behavior on random data. Theoretical analysis by Dobosiewicz and others has shown that with a shrink factor of 1.3, the algorithm's performance is significantly better than O(n²) but does not guarantee O(n log n) for all inputs. For this reason, some textbooks conservatively list Comb Sort's average case as O(n²) or O(n²/2^p) to reflect that it remains a quadratic algorithm in the same family as Bubble Sort, albeit with a much smaller constant factor.

The number of passes is logarithmic. Since the gap is divided by 1.3 each time, the number of distinct gap values is log_1.3(n), which is approximately 3.8 * log₂(n). Each pass does O(n) comparisons, so the total work before the final gap=1 phase is O(n log n). The final gap=1 phase is essentially Bubble Sort on a nearly-sorted array, which is O(n) if only one or two passes are needed, but could be O(n²) in the worst case.

Variations and Optimizations

While the basic Comb Sort is already a substantial improvement over Bubble Sort, several variations have been proposed to further enhance its performance, stability, or applicability.

Comb Sort 11

As implemented earlier, Comb Sort 11 is the most famous optimization. During testing, the authors discovered that the algorithm's efficiency drops when the gap becomes 9 or 10. These gaps appear to be less effective at eliminating remaining inversions, leading to more work in the final gap=1 phase. The fix is simple: if the calculated gap is 9 or 10, set it to 11 instead. This single rule consistently improves performance by a few percent and is now considered part of the standard definition of Comb Sort in many references.

Different Shrink Factors and Gap Sequences

Although 1.3 is optimal for random data, other shrink factors can be better for specific data types. Some implementations use 1.247... which is derived from more precise mathematical optimization, while others experiment with dynamic shrink factors that adapt based on the number of swaps in the previous pass. For example, if a pass had many swaps, the shrink factor could be kept smaller to allow more thorough combing at that scale. Another approach is to precompute an optimal gap sequence similar to Shell Sort's Ciura sequence, rather than calculating it dynamically by division.

Early Termination and Cocktail Comb Sort

An optimization borrowed from Cocktail Shaker Sort (bidirectional Bubble Sort) can be applied. Instead of always scanning left-to-right, the algorithm can alternate direction each pass. This helps handle both turtles and rabbits symmetrically, though Comb Sort already handles turtles well, so the benefit is modest. A more impactful optimization is to track the last swap position. If the last swap in a gap=1 pass occurred at index k, the next pass only needs to scan up to k, as elements beyond k are already sorted. This reduces unnecessary comparisons on the tail end of the array.

Stable Comb Sort

The standard algorithm is unstable. To make it stable, one must avoid swapping equal elements and ensure that the gap sequence does not reorder equal keys. However, achieving true stability while retaining the gap mechanism is difficult and usually requires additional memory, such as storing the original index as a tie-breaker. In practice, if stability is required, it is better to choose a naturally stable algorithm like Mergesort or Insertion Sort.

Real-World Applications

Comb Sort is rarely found in the standard library of a major programming language — Python's Timsort, Java's Dual-Pivot Quicksort, and C++'s Introsort are far more sophisticated. However, its simplicity, low memory footprint, and decent average performance make it suitable for specific real-world niches where those industrial-strength algorithms would be overkill.

In embedded systems and microcontroller programming, memory is extremely constrained and code size matters. Implementing a full Quicksort with recursion and stack management may be impractical on a device with a few kilobytes of RAM. Comb Sort can be implemented in under 20 lines of C with no recursion and O(1) extra space, making it ideal for sorting small sensor readings, log entries, or configuration arrays on Arduino, ARM Cortex-M, or similar platforms.

For educational tools and visualizations, Comb Sort is an excellent teaching aid. It visually demonstrates the concept of gap-based sorting and serves as a stepping stone to understanding more complex algorithms like Shell Sort. Many algorithm visualization websites and university courses use Comb Sort to illustrate how a small change to Bubble Sort yields a large performance gain, reinforcing lessons about algorithm design and analysis.

In situations involving small or nearly sorted datasets, Comb Sort can outperform more complex algorithms due to lower overhead. For example, a web server that needs to sort a list of 50-100 active session timestamps or a game engine sorting a small list of sprites by depth (z-order) each frame may find that Comb Sort's simple loops are faster in practice than the recursive calls and partitioning logic of Quicksort, where constant factors dominate for small n.

Where Not to Use Comb Sort

Comb Sort should not be used for large-scale data processing, database indexing, or any application where worst-case guarantees are critical. Its O(n²) worst case and lack of stability make it unsuitable for sorting millions of records or for use as a general-purpose library sort. In those contexts, O(n log n) worst-case algorithms like Mergesort or Heapsort, or highly optimized hybrid sorts like Timsort, are the correct choice. Additionally, if sorting is a bottleneck in a network service or database engine, the extra engineering effort to implement a faster algorithm will pay significant dividends.

Comparison with Alternatives

To choose the right sorting algorithm, it is essential to understand how Comb Sort compares to its relatives and competitors across key dimensions: time complexity, space usage, stability, and implementation complexity.

Bubble Sort is the direct predecessor. Comb Sort dominates it in every performance metric while retaining the same O(1) space and simple implementation. There is almost no reason to use Bubble Sort today if Comb Sort is available. Insertion Sort, another O(n²) algorithm, is actually faster than Comb Sort on very small (n < 20) or nearly sorted arrays due to its adaptive nature and low constant factors, but Comb Sort wins on larger random arrays.

Shell Sort is the closest conceptual cousin. Both use a diminishing gap sequence, but Shell Sort sorts each gapped subarray using Insertion Sort, while Comb Sort uses a single bubble-style pass. Shell Sort with a good gap sequence (like Ciura or Tokuda) is generally faster than Comb Sort and has better theoretical bounds, but it is slightly more complex to implement. Quicksort and Mergesort are in a different league, offering O(n log n) average/worst-case performance and are the standard for general-purpose sorting, but they require more code, recursion, and in the case of Mergesort, O(n) extra space.

The table makes it clear that Comb Sort occupies a middle ground: it is a simple, in-place, turtle-resistant upgrade to Bubble Sort that approaches the performance of Shell Sort without its slightly more involved inner insertion sort. It is not a replacement for Quicksort or Timsort for large-scale sorting, but it is a superior choice whenever Bubble Sort might have been considered.

Common Mistakes and Best Practices

Despite its simplicity, developers frequently introduce subtle bugs or performance pitfalls when implementing Comb Sort. Awareness of these common mistakes is key to a correct and efficient implementation.

Mistake 1: Incorrect Gap Update or Integer Division. A frequent error is to use floating-point division without truncating, or to update the gap incorrectly. The gap must be an integer and should be calculated as `gap = int(gap / shrink)`. Using `gap //= shrink` with a float shrink can cause type errors, and forgetting to handle the case where gap becomes 0 will cause an infinite loop or index error. Always ensure gap is at least 1 before the inner loop.

Mistake 2: Wrong Termination Condition. Many novices stop the algorithm as soon as gap == 1, without verifying that a full pass with gap=1 required no swaps. This leaves the array potentially unsorted. The correct logic is to continue looping with gap=1 until a complete pass makes zero swaps. The boolean flag must be set to True only when gap==1 and then falsified if any swap occurs.

Mistake 3: Forgetting the Comb Sort 11 Rule. While not a correctness bug, omitting the gap 9/10 → 11 optimization leaves performance on the table. It is a one-line check that should be included in any production version. Similarly, using a shrink factor of 2.0 (halving the gap) is a common but suboptimal choice that degrades performance.

Mistake 4: Assuming Stability. Developers sometimes use Comb Sort to sort records with multiple keys, expecting equal keys to retain their original order. Because Comb Sort is unstable, this assumption will lead to subtle data corruption. If stability is required, either use a stable algorithm or augment the comparison to include the original index as a secondary key.

Best Practices

• Use Shrink Factor 1.3 and Comb 11: Treat these as the default. They are empirically validated and cost nothing to implement.
• Implement In-Place, But Return for Convenience: Sort the list in place to maintain O(1) space, but return the list to allow chaining and testing.
• Add Type Hints and Docstrings: For Python code, annotate the function signature (e.g., `def comb_sort(arr: list) -> list:`) and document the shrink factor and stability characteristics.
• Test Edge Cases: Always test with empty lists, single-element lists, already sorted lists, reverse-sorted lists, lists with duplicates, and lists with negative numbers.
• Benchmark Before Deploying: For n > 1000, benchmark Comb Sort against Python's built-in `list.sort()` (Timsort). The built-in will almost always be faster due to its C implementation and superior algorithm. Use Comb Sort only where its simplicity or memory constraints justify it.
• Avoid Recursion: One of Comb Sort's advantages is its iterative nature. Do not introduce recursion, which would add stack overhead and risk stack overflow.

Interview Questions

Comb Sort is a popular topic in technical interviews because it tests understanding of Bubble Sort, gap-based optimization, complexity analysis, and practical trade-offs. Here are common questions and how to answer them effectively.

1. How does Comb Sort improve upon Bubble Sort, and what problem does it solve?

Answer: Bubble Sort only compares adjacent elements, so small elements at the end of the array (turtles) move backward very slowly — one position per pass, leading to O(n²) time. Comb Sort introduces a gap that starts at n and shrinks by a factor of ~1.3 each pass. By comparing elements far apart early, it allows turtles to jump long distances in a single swap. Early passes with large gaps quickly move elements to their approximate correct region, leaving only local inversions for the final gap=1 bubble pass to clean up. This reduces average time from O(n²) to empirically O(n log n) while keeping O(1) space and simple code.

2. What is the shrink factor, why is 1.3 used, and what is Comb Sort 11?

Answer: The shrink factor determines how quickly the gap decreases: `gap = int(gap / shrink)`. A factor too large shrinks too fast and misses opportunities for long swaps; too small creates too many passes. Through extensive empirical testing, 1.3 was found to be optimal for random data. Comb Sort 11 is an optimization where if the gap becomes 9 or 10, it is set to 11 instead. Gaps of 9 and 10 were found to be inefficient at removing remaining inversions, and forcing them to 11 yields a measurable speedup. Any good implementation should include this rule.

3. What are the time and space complexities of Comb Sort? Is it stable?

Answer: Space is O(1) auxiliary as it sorts in place. Time is O(n log n) best case (already sorted, still checks all gaps), O(n²) worst case (pathological input where final bubble phase does O(n²) work), and empirically O(n log n) or O(n²/2^p) average case on random data — much better than Bubble Sort's O(n²) average. It is not stable because distant swaps can reorder equal elements. For example, sorting [2_a, 2_b, 1] with a large gap could swap 2_a with 1, placing 2_b before 2_a. If stability is needed, use Mergesort or Insertion Sort.

4. Walk through Comb Sort on [5, 1, 4, 2, 8] with shrink 1.3.

Answer: n=5, initial gap=5. Pass 1: gap=int(5/1.3)=3. Compare 5 vs 2 → swap → [2,1,4,5,8]; 1 vs 8 → no swap. Pass 2: gap=int(3/1.3)=2. Compare 2 vs 4 → no swap; 1 vs 5 → no swap; 4 vs 8 → no swap. Pass 3: gap=int(2/1.3)=1. Now bubble phase: 2 vs 1 → swap → [1,2,4,5,8]; 2 vs 4 no swap; 4 vs 5 no swap; 5 vs 8 no swap. Need another gap=1 pass to verify no swaps → array sorted. This shows how gap=3 immediately moved 2 from index 3 to index 0.

5. When would you choose Comb Sort over Quicksort or Python's built-in sort?

Answer: I would almost never choose Comb Sort over Timsort/Quicksort for large or general-purpose sorting — those are O(n log n) worst-case (or average) with highly optimized implementations. I would choose Comb Sort when: (a) code simplicity and minimal memory are paramount, such as on embedded microcontrollers with no recursion and O(1) space; (b) sorting small arrays (e.g., n < 200) where constant factors matter and Comb Sort's low overhead beats Quicksort's partitioning; (c) for educational purposes or quick prototyping where writing a correct sort in under 20 lines is more valuable than absolute speed. For production Python code sorting large data, always use `list.sort()`.