15.21 Testing Divide-and-Conquer Algorithms

Problem

Divide-and-conquer algorithms are prone to subtle implementation errors. The high-level idea may be correct, but bugs often appear in:

base cases
split boundaries
merge logic
pivot handling
recursive termination
index ranges
temporary buffers

These bugs may not appear on ordinary examples. A merge sort can pass random tests while failing on duplicates. A binary search can work for most inputs while looping forever on a two-element range. A closest-pair implementation can pass small examples while missing points near the split line.

How do you test divide-and-conquer code systematically?

Solution

Test the algorithm at three levels:

Test the public function against a trusted baseline.
Test helper operations such as merge, partition, and feasibility checks directly.
Test boundary cases that stress recursion structure.

For many algorithms, the best baseline is a slow brute-force implementation. It may be too slow for production, but it is usually simple enough to trust on small inputs.

The testing strategy is:

generate many small inputs
compare fast algorithm against brute force
include hand-picked edge cases
test helper invariants
test large inputs for performance and stack safety

This catches both correctness bugs and implementation pathologies.

Use a Brute-Force Oracle

A brute-force algorithm is often the simplest specification.

For inversion counting:

func CountInversionsBrute(nums []int) int64 {
    var count int64

    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] > nums[j] {
                count++
            }
        }
    }

    return count
}

The optimized divide-and-conquer version can be tested against it.

func TestCountInversionsAgainstBrute(t *testing.T) {
    cases := [][]int{
        {},
        {1},
        {1, 2},
        {2, 1},
        {1, 1},
        {3, 2, 1},
        {2, 4, 1, 3, 5},
    }

    for _, nums := range cases {
        got := CountInversions(nums)
        want := CountInversionsBrute(nums)

        if got != want {
            t.Fatalf("nums=%v got=%d want=%d",
                nums, got, want)
        }
    }
}

The brute-force version is not a competitor. It is a correctness oracle.

Randomized Differential Testing

Hand-written cases are useful but incomplete.

Randomized testing generates many small cases automatically.

func TestCountInversionsRandom(t *testing.T) {
    rng := rand.New(rand.NewSource(1))

    for trial := 0; trial < 10000; trial++ {
        n := rng.Intn(12)
        nums := make([]int, n)

        for i := range nums {
            nums[i] = rng.Intn(7) - 3
        }

        got := CountInversions(nums)
        want := CountInversionsBrute(nums)

        if got != want {
            t.Fatalf("trial=%d nums=%v got=%d want=%d",
                trial, nums, got, want)
        }
    }
}

Small arrays are enough to reveal most boundary errors because the recursion still exercises:

empty ranges
single elements
odd splits
even splits
duplicates
negative values

A fixed seed makes failures reproducible.

Test Helper Invariants

Many divide-and-conquer algorithms depend on one critical helper.

Examples:

Algorithm	Critical Helper
Merge sort	merge
Quick sort	partition
Quickselect	partition
Closest pair	strip scan
Binary search on answer	feasibility check
FFT	inverse transform
Offline queries	range decomposition

Test these helpers directly.

For partition:

func TestPartitionInvariant(t *testing.T) {
    nums := []int{9, 4, 7, 3, 10, 5}

    p := partition(nums, 0, len(nums)-1)

    pivot := nums[p]

    for i := 0; i < p; i++ {
        if nums[i] >= pivot {
            t.Fatalf("left violation: nums=%v p=%d",
                nums, p)
        }
    }

    for i := p + 1; i < len(nums); i++ {
        if nums[i] < pivot {
            t.Fatalf("right violation: nums=%v p=%d",
                nums, p)
        }
    }
}

This test does not require the whole quick sort to run. It verifies the local contract that quick sort depends on.

Test Boundary Sizes

Divide-and-conquer algorithms often fail around small sizes.

Always include:

n = 0
n = 1
n = 2
n = 3
n = 4

These sizes stress:

base cases
midpoint calculation
empty halves
one-element halves
off-by-one recursion

Example for sorting:

func TestMergeSortSmallSizes(t *testing.T) {
    cases := [][]int{
        {},
        {1},
        {2, 1},
        {2, 1, 3},
        {4, 3, 2, 1},
    }

    for _, nums := range cases {
        got := MergeSort(append([]int(nil), nums...))
        want := append([]int(nil), nums...)
        sort.Ints(want)

        if !reflect.DeepEqual(got, want) {
            t.Fatalf("nums=%v got=%v want=%v",
                nums, got, want)
        }
    }
}

Small inputs are where termination bugs live.

Test Duplicates

Duplicates are a frequent source of partition and comparison errors.

Use cases such as:

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

For sorting, duplicates test stability if stability is part of the contract.

For inversion counting, duplicates test whether equal elements are incorrectly counted.

For quickselect, duplicates test whether the algorithm makes progress.

For closest-pair, duplicate points should return distance zero.

Test Already Sorted and Reverse Sorted Inputs

Sorted inputs often reveal worst-case quick sort behavior.

[1, 2, 3, 4, 5]

Reverse-sorted inputs stress different boundaries:

[5, 4, 3, 2, 1]

These cases are important because many partition schemes perform badly when the pivot is chosen from one end.

For randomized algorithms, use fixed seeds so failures are reproducible.

Test Mutation Contracts

Some algorithms mutate input.

Examples:

quick sort
quickselect
in-place partition
in-place transpose

Others should preserve input.

Examples:

functional merge sort
counting inversions with copied work array
closest pair

Make this contract explicit.

func TestCountInversionsDoesNotMutateInput(t *testing.T) {
    nums := []int{2, 4, 1, 3, 5}
    original := append([]int(nil), nums...)

    _ = CountInversions(nums)

    if !reflect.DeepEqual(nums, original) {
        t.Fatalf("input mutated: got=%v want=%v",
            nums, original)
    }
}

Mutation bugs are especially costly when algorithms are used as library functions.

Test Index-Based APIs

Index-based recursive functions are efficient but easy to misuse.

For a function:

QuickSort(nums, low, high)

test subranges, not only whole arrays.

func TestQuickSortSubrange(t *testing.T) {
    nums := []int{99, 4, 3, 2, 1, 88}

    QuickSort(nums, 1, 4)

    want := []int{99, 1, 2, 3, 4, 88}

    if !reflect.DeepEqual(nums, want) {
        t.Fatalf("got=%v want=%v", nums, want)
    }
}

This catches functions that accidentally sort outside their assigned range.

Test Recursive Termination

Some bugs do not return wrong answers. They fail to return at all.

Common sources:

midpoint does not shrink interval
pivot included in recursive calls
binary search updates do not advance
empty range not handled
duplicate values trap partition loops

Use tests with timeouts for suspicious code.

func TestBinarySearchTerminates(t *testing.T) {
    nums := []int{1, 3}

    done := make(chan struct{})

    go func() {
        _ = BinarySearch(nums, 2)
        close(done)
    }()

    select {
    case <-done:
        return
    case <-time.After(100 * time.Millisecond):
        t.Fatal("binary search did not terminate")
    }
}

This is not needed for every test, but it is useful when developing low-level recursive code.

Property-Based Testing

Property-based tests assert general facts rather than individual outputs.

For sorting:

output is sorted
output is a permutation of input

For partition:

left side satisfies predicate
right side satisfies predicate
pivot is placed between them

For FFT:

IFFT(FFT(x)) approximately equals x

For range queries:

query result equals brute-force scan

A property test can generate hundreds or thousands of inputs automatically.

Approximate Equality for Floating-Point Algorithms

Algorithms such as FFT and closest-pair distance may use floating-point arithmetic.

Do not compare floating-point results with exact equality unless the values are known to be exact.

Use a tolerance.

func almostEqual(a, b float64) bool {
    const eps = 1e-9
    return math.Abs(a-b) <= eps
}

For FFT-based integer convolution, round results before comparison.

For geometric algorithms, compare squared distances when possible.

Large-Input Tests

Correctness tests should use small inputs and brute-force oracles.

Performance tests should use large inputs.

Examples:

1 million elements for sorting
100 thousand points for closest pair
large exponent for modular exponentiation
large query batch for offline queries

Large tests reveal:

stack overflows
excessive allocation
poor pivot selection
slow combine steps
cache-unfriendly implementations

Do not use brute force here. Use known invariants and runtime measurements.

Benchmark Against Baselines

A divide-and-conquer algorithm should be compared with a simple baseline.

Example:

func BenchmarkMergeSort(b *testing.B) {
    input := randomArray(1_000_000)

    b.ResetTimer()

    for i := 0; i < b.N; i++ {
        nums := append([]int(nil), input...)
        _ = MergeSort(nums)
    }
}

Compare against:

sort.Ints

or another trusted implementation.

Benchmarking tells you whether your theoretically faster algorithm is actually faster in the intended range.

Test Cutoff Thresholds

Hybrid algorithms often use thresholds.

Examples:

Karatsuba switches to grade-school multiplication
Strassen switches to classical multiplication
parallel sort switches to sequential sort
recursive transpose switches to iterative kernel

Test around the cutoff:

threshold - 1
threshold
threshold + 1

These are common failure points.

Common Mistakes

Testing Only Random Inputs

Random tests may miss sorted, reverse-sorted, duplicate-heavy, and empty inputs.

Use both random and hand-picked tests.

Testing Only the Final Output

Helper invariants catch bugs earlier and make failures easier to diagnose.

Ignoring Mutation

Document and test whether the algorithm mutates its input.

Using Large Inputs with Brute Force

Brute force belongs in small randomized tests.

Large tests need invariants and benchmarks.

Comparing Floats Exactly

Use tolerances for numerical algorithms.

Discussion

Testing divide-and-conquer algorithms works best when it mirrors the proof structure. The whole algorithm should be compared against a trusted baseline. The helper that performs the combine step should be tested by its local invariant. Boundary cases should attack the recursion.

This approach is practical because most divide-and-conquer bugs are not mysterious. They come from incorrect base cases, wrong split points, broken merge logic, or recursive calls that do not shrink the problem. A disciplined test suite exposes those failures quickly.

The most useful pattern is differential testing on small inputs. Write the simplest correct version first, even if it is slow. Then use it as an oracle for the optimized version. This gives you confidence that the divide-and-conquer implementation preserves correctness while improving performance.