# 6.23 Testing Sort Correctness

# 6.23 Testing Sort Correctness

Sorting implementations are easy to get almost right and hard to get completely correct. Subtle bugs often appear only on edge cases, duplicate-heavy inputs, or adversarial patterns. A disciplined testing strategy verifies both the ordering and permutation properties under a wide range of inputs.

## Problem

You have implemented a sorting algorithm. You want to verify that it is correct, stable when required, and robust across inputs.

## Core Properties to Test

Every sorting algorithm must satisfy two fundamental properties:

**Order condition**

```text id="o7k2p9"
for all i:
  A[i] <= A[i+1]
```

**Permutation condition**

The output must contain exactly the same elements as the input.

These two properties are independent. Passing one does not imply the other.

## Minimal Test Oracle

A simple correctness checker:

```text id="m8d4vn"
is_sorted(A):
  for i = 0 to n - 2:
    if A[i] > A[i+1]:
      return false
  return true
```

Permutation check using frequency maps:

```text id="k1t8rc"
same_multiset(A, B):
  countA = frequency_map(A)
  countB = frequency_map(B)
  return countA == countB
```

Combined test:

```text id="v2f3jq"
check_sort(input, output):
  assert is_sorted(output)
  assert same_multiset(input, output)
```

## Stability Testing

If stability is required, test that equal keys preserve input order.

Decorate each element with its original index:

```text id="r7y6df"
input = [(value, index)]
```

After sorting by `value`, verify:

```text id="g4c9mn"
for all equal values:
  indices are in increasing order
```

This detects whether equal elements have been reordered.

## Edge Cases

Test boundary inputs explicitly:

```text id="z1k9pf"
empty array
single element
two elements (sorted and unsorted)
all elements equal
already sorted
reverse sorted
alternating high and low values
```

These cases often expose off-by-one errors and incorrect comparisons.

## Adversarial Inputs

Some algorithms degrade on specific patterns.

Examples:

```text id="w8y3tb"
sorted input (quick sort worst case)
reverse sorted input
many duplicates (partition issues)
nearly sorted (adaptive behavior)
```

Generate inputs that stress the algorithm’s weak points.

## Random Testing

Randomized testing covers a wide input space.

```text id="d5s2xr"
for many trials:
  A = random array
  B = sort(A)
  check_sort(A, B)
```

Use different distributions:

```text id="y6c8ua"
uniform random
small integer range (many duplicates)
large integer range
skewed distributions
```

Random testing often reveals bugs missed by fixed test cases.

## Differential Testing

Compare against a trusted implementation.

```text id="q3m1kp"
reference = built_in_sort(A)
test = your_sort(A)
assert reference == test
```

This is powerful because the reference implementation handles many edge cases correctly.

## Property-Based Testing

Instead of fixed inputs, define properties:

```text id="h2n7sv"
sorted output is nondecreasing
output length equals input length
output contains same elements
```

Generate random inputs and verify properties automatically.

Frameworks such as QuickCheck-style systems automate this approach.

## Large Input Testing

Test performance and correctness on large arrays:

```text id="x8u0pq"
n = 10^5 or higher
random and structured inputs
```

This reveals:

* performance issues
* stack overflow (recursive algorithms)
* memory allocation problems

## Floating-Point Testing

If sorting floating-point values, test special cases:

```text id="k7z3av"
NaN values
+0 and -0
infinity
very large and very small values
```

Define a consistent comparison policy. Many languages treat `NaN` as unordered.

## Comparator Testing

If using custom comparators, verify:

```text id="n5c2wr"
transitivity
symmetry
consistency across calls
```

Incorrect comparators can break otherwise correct sorting algorithms.

## Regression Tests

When a bug is found, add the failing input to a regression suite:

```text id="p9v4qx"
test_cases.append(failing_input)
```

This ensures the bug does not reappear after future changes.

## Performance Testing

Measure runtime for different input sizes and patterns:

```text id="r3t7ok"
vary n
vary distribution
record time
```

Check that performance matches expected complexity:

```text id="c8q1bd"
O(n log n) for general sorts
O(n) for counting or radix under constraints
```

Unexpected slowdowns often indicate hidden inefficiencies.

## Common Bugs

* Off-by-one errors in loops
* Incorrect pivot handling in quick sort
* Unstable behavior when stability is required
* Losing elements during swaps or merges
* Incorrect handling of duplicates
* Incorrect boundary conditions in partitioning

## Takeaway

Sorting correctness depends on verifying order, permutation, and optionally stability. Combine edge cases, random testing, and differential testing to build confidence in the implementation.