Skip to content

6.23 Testing Sort Correctness

Verify both the ordering and permutation properties of sorting implementations using randomized, edge-case, and adversarial test strategies.

algorithms sorting testing 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

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:

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

Permutation check using frequency maps:

same_multiset(A, B):
  countA = frequency_map(A)
  countB = frequency_map(B)
  return countA == countB

Combined test:

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:

input = [(value, index)]

After sorting by value, verify:

for all equal values:
  indices are in increasing order

This detects whether equal elements have been reordered.

Edge Cases

Test boundary inputs explicitly:

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:

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.

for many trials:
  A = random array
  B = sort(A)
  check_sort(A, B)

Use different distributions:

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.

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:

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:

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:

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:

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:

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:

vary n
vary distribution
record time

Check that performance matches expected complexity:

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.