15.22 Common Bugs

Divide-and-conquer algorithms often fail in ways that are difficult to see from the high-level design.

algorithmsdivide-and-conquerrecursion

15.22 Common Bugs

Problem

Divide-and-conquer algorithms often fail in ways that are difficult to see from the high-level design.

The recurrence may be correct. The idea may be standard. The code may even work for ordinary examples.

Then a small input breaks it:

[]
[1]
[2, 1]
[1, 1, 1]

or a boundary case causes:

infinite recursion
missing element
duplicate element
wrong pivot position
stack overflow
incorrect count

How do you recognize and avoid the most common divide-and-conquer bugs?

Solution

Look for bugs at the three structural points of the algorithm:

base case
split
combine

Most failures occur because one of these is slightly wrong.

A reliable review checklist is:

  1. Does every recursive path reach a base case?
  2. Are subproblems strictly smaller?
  3. Are all elements included exactly once?
  4. Does the combine step preserve the intended invariant?
  5. Are boundary indexes inclusive or exclusive consistently?
  6. Does the algorithm handle duplicates?
  7. Does the implementation match the complexity analysis?

Bug 1: Base Case Too Narrow

A common recursive bug is stopping too late.

Bad merge sort:

func MergeSort(nums []int) []int {
    if len(nums) == 1 {
        return nums
    }

    mid := len(nums) / 2

    left := MergeSort(nums[:mid])
    right := MergeSort(nums[mid:])

    return Merge(left, right)
}

This fails for:

[]

because:

len(nums) == 1

is false.

Then:

mid = 0
left = []
right = []

and recursion never makes progress.

Better:

func MergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }

    mid := len(nums) / 2

    left := MergeSort(nums[:mid])
    right := MergeSort(nums[mid:])

    return Merge(left, right)
}

Use base cases that cover all minimal inputs.

Bug 2: Recursive Calls Do Not Shrink

Every recursive call must receive a strictly smaller problem.

Bad binary search:

func Search(nums []int, target int, low, high int) int {
    if low > high {
        return -1
    }

    mid := low + (high-low)/2

    if nums[mid] == target {
        return mid
    }

    if nums[mid] < target {
        return Search(nums, target, mid, high)
    }

    return Search(nums, target, low, mid)
}

When low + 1 == high, mid may equal low.

The recursive call:

Search(nums, target, mid, high)

can repeat the same interval.

Correct version:

func Search(nums []int, target int, low, high int) int {
    if low > high {
        return -1
    }

    mid := low + (high-low)/2

    if nums[mid] == target {
        return mid
    }

    if nums[mid] < target {
        return Search(nums, target, mid+1, high)
    }

    return Search(nums, target, low, mid-1)
}

Exclude the midpoint after checking it.

Bug 3: Inclusive and Exclusive Bounds Mixed

Index bugs often come from mixing conventions.

Two common styles are:

inclusive: [low, high]
exclusive: [low, high)

Both are valid. Mixing them is dangerous.

Exclusive style:

func sortRange(a []int, lo, hi int) {
    if hi-lo <= 1 {
        return
    }

    mid := lo + (hi-lo)/2

    sortRange(a, lo, mid)
    sortRange(a, mid, hi)
}

Inclusive style:

func sortRange(a []int, low, high int) {
    if low >= high {
        return
    }

    mid := low + (high-low)/2

    sortRange(a, low, mid)
    sortRange(a, mid+1, high)
}

Choose one convention and keep it through the function.

Bug 4: Lost Elements During Merge

A merge loop that stops when one side is exhausted must still copy the remaining side.

Buggy merge:

func Merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))

    i, j := 0, 0

    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    return result
}

For:

left  = [1, 4]
right = [2]

this returns:

[1, 2]

and loses:

4

Correct:

result = append(result, left[i:]...)
result = append(result, right[j:]...)

A merge function should preserve element count.

Always test:

len(output) == len(left) + len(right)

Bug 5: Duplicate Handling in Partition

Simple quicksort partitioning often assumes distinct values.

Bad partition logic may fail or degrade badly on:

[5, 5, 5, 5, 5]

If recursive calls do not exclude the pivot or equal region properly, duplicates can cause infinite recursion or quadratic behavior.

For duplicate-heavy input, use three-way partitioning:

< pivot
== pivot
> pivot

Then recurse only on the less-than and greater-than regions.

This avoids repeatedly processing elements equal to the pivot.

Bug 6: Broken Stability

If a sorting algorithm promises stability, equal elements must keep their original order.

In merge sort, this detail matters:

if left[i] <= right[j] {
    result = append(result, left[i])
    i++
} else {
    result = append(result, right[j])
    j++
}

Using:

if left[i] < right[j]

chooses the right element first when values are equal.

That can break stability.

The algorithm may still sort correctly, but it no longer satisfies the stronger contract.

Bug 7: Wrong Midpoint Calculation

This expression is common:

mid := (low + high) / 2

For large integer indexes, low + high may overflow.

Safer:

mid := low + (high-low)/2

Many modern languages and input sizes make overflow less likely, but the safer form costs nothing and avoids a class of bugs.

Bug 8: Wrong Recurrence Due to Copying

A clean-looking implementation can accidentally copy too much data.

Example:

left := append([]int(nil), nums[:mid]...)
right := append([]int(nil), nums[mid:]...)

This copies at every recursive call.

For merge sort, copying subarrays plus allocating merge results can still be asymptotically acceptable, but the constant factor may be large.

For other algorithms, copying can change expected performance significantly.

Prefer index ranges or reusable buffers in production.

Bug 9: Assuming Balanced Splits

Some algorithms split evenly.

Merge sort:

n/2 and n/2

Some do not.

Quick sort:

pivot position determines split

If pivot selection is poor, quick sort may produce:

0 and n-1

repeatedly.

That gives:

$$ O(n^2) $$

time and:

$$ O(n) $$

stack space.

Do not claim balanced complexity unless the algorithm guarantees balanced splits or uses randomization with expected analysis.

Bug 10: Off-by-One in Quickselect Rank

Users often define:

k = 1

as the smallest element.

Array indexes define:

index 0

as the first element.

Convert once:

target := k - 1

Then use target consistently.

For the (k)-th largest element:

target := len(nums) - k

Mixing rank and index causes errors that only appear for boundary values like first, last, and median.

Bug 11: Incorrect Strip Condition in Closest Pair

In closest-pair algorithms, the strip should include points whose x-coordinate is within the current best distance of the dividing line.

Typical condition:

if math.Abs(p.X-midX) < best {
    strip = append(strip, p)
}

Using the wrong coordinate, wrong midpoint, or wrong inequality can miss valid crossing pairs.

Another mistake is sorting the strip by x-coordinate. The strip scan depends on y-ordering.

Bug 12: Floating-Point Equality

Geometric and FFT algorithms often use floating-point numbers.

Bad test:

if got != want {
    t.Fatal("wrong")
}

Better:

if math.Abs(got-want) > 1e-9 {
    t.Fatal("wrong")
}

For distance comparisons, use squared distances to avoid unnecessary square roots and reduce numerical noise.

For FFT coefficient recovery, round values that should be integral.

Bug 13: Forgetting to Pad FFT Inputs

FFT-based convolution requires enough space for the full result.

If:

len(a) = m
len(b) = n

the result has:

m + n - 1

coefficients.

Pad to at least that length, often the next power of two.

Without padding, convolution wraps around.

This produces plausible but wrong results.

Bug 14: Stack Overflow

Recursive algorithms can exhaust the call stack.

Common causes:

  • worst-case quick sort
  • missing base case
  • recursive call does not shrink
  • very deep binary recursion over linked structures
  • input size too large for recursive implementation

Mitigations:

  • convert to iterative form
  • recurse into smaller partition first
  • use explicit stack
  • randomize pivots
  • add depth limits

Introsort uses a depth limit and switches strategy when recursion becomes suspicious.

Bug 15: Parallel Data Races

Parallel divide-and-conquer introduces concurrency bugs.

Bad pattern:

all workers append to shared result

Better pattern:

each worker writes to a disjoint range
combine after join

For parallel algorithms, verify:

  • no overlapping writes
  • no shared mutable state without synchronization
  • no goroutine leaks
  • no unbounded task creation
  • no false sharing in hot counters

Correct sequential code can become incorrect after naive parallelization.

Review Checklist

Before trusting a divide-and-conquer implementation, check:

Area Question
Base case Does it handle empty and single-element input?
Progress Does every recursive call shrink the problem?
Bounds Are indexes consistently inclusive or exclusive?
Coverage Are all elements included exactly once?
Combine Does the merge or partition preserve its invariant?
Duplicates Are equal values handled deliberately?
Mutation Does the function mutate input, and is that documented?
Space Are allocations intentional?
Worst case Can recursion become unbalanced?
Tests Is there a brute-force oracle for small inputs?

Discussion

Most divide-and-conquer bugs are structural. They are not caused by misunderstanding the algorithm at a high level. They arise because an implementation fails to preserve one of the small contracts that make recursion safe: base cases must stop, splits must shrink, combines must preserve data, and boundaries must be consistent.

The best defense is to make each contract explicit. Write helper functions with narrow responsibilities. Test merge, partition, feasibility, and strip scanning independently. Compare the whole algorithm against brute force on small randomized inputs. Include empty, duplicate-heavy, sorted, and reverse-sorted cases.

Divide-and-conquer code becomes reliable when its recursion shape is boring. The base case is obvious, the split convention is consistent, and the combine step has a clear invariant. Once those pieces are stable, the larger algorithm usually follows.