6.24 Common Bugs

Sorting bugs usually come from boundary errors, invalid invariants, or misunderstood comparison rules. Many implementations work on ordinary random inputs but fail on empty arrays, duplicate-heavy arrays, reverse sorted arrays, or arrays with custom records.

Problem

You have a sorting implementation that appears correct on common inputs. You want to identify the failure patterns that most often break sorting algorithms.

Off-by-One Errors

Sorting code frequently works with ranges. A common convention is the half-open interval:

[lo, hi)

This means lo is included and hi is excluded. The length is:

hi - lo

The base case is usually:

if hi - lo <= 1:
  return

A common bug is mixing this with a closed interval:

[lo, hi]

If one helper expects [lo, hi) and another expects [lo, hi], the algorithm may skip the last element, process one element twice, or read out of bounds.

Incorrect Partition Bounds

Quick sort and quickselect depend on excluding the pivot after partitioning.

If partition returns pivot index p, the recursive calls should usually be:

quick_sort(A, lo, p)
quick_sort(A, p + 1, hi)

A common incorrect version is:

quick_sort(A, lo, p)
quick_sort(A, p, hi)

This may recurse forever when p = lo.

Duplicate Handling

Duplicates expose weak partition logic. A two-way partition may fail to shrink the problem if equal elements are repeatedly placed on the wrong side.

For duplicate-heavy input, three-way partitioning is often safer:

elements < pivot
elements = pivot
elements > pivot

This avoids recursively sorting the equal region.

Stability Mistakes

A sort can be correct but unstable. The output is ordered and contains the same elements, yet equal-key records may be reordered.

Common stability bugs:

insertion sort shifts A[j] >= key instead of A[j] > key
merge sort takes from the right half when keys are equal
selection sort swaps a later minimum past equal elements

Stability must be tested with records, not plain numbers.

Comparator Bugs

A sorting algorithm assumes the comparator is consistent. If the comparator violates transitivity, no sorting algorithm can guarantee correct output.

Bad comparator pattern:

compare(a, b) changes result across calls

This happens when comparison depends on mutable state, time, randomness, or external data that changes during sorting.

Another bug is subtracting integers to compare:

return a - b

This can overflow. Use explicit comparison instead:

if a < b: return -1
if a > b: return 1
return 0

Losing Elements During Merge

Merge sort often fails because data is copied into a buffer but not copied back correctly.

Incorrect merge code may:

overwrite unread input
forget remaining elements
copy too many elements
copy too few elements

A good merge implementation should have clear source and destination ranges.

Wrong Heap Size

Heap sort bugs often come from including the sorted suffix in heap operations.

After swapping the max element into position end, the heap range must shrink:

sift_down(A, 0, end)

not:

sift_down(A, 0, n)

Including the sorted suffix destroys already placed elements.

Integer Overflow

Sorting algorithms compute midpoints, counts, and ranks. These values can overflow fixed-width integers.

Risky midpoint:

mid = (lo + hi) / 2

Safer midpoint:

mid = lo + (hi - lo) / 2

Inversion counting also requires wide integers because the maximum inversion count is:

n(n - 1) / 2

Unsigned Index Underflow

Insertion sort often decrements an index below zero.

Bug-prone pattern:

j = i - 1
while j >= 0 and A[j] > key:
  ...
  j = j - 1

If j is unsigned, j >= 0 is always true. When j reaches zero and decrements, it wraps to a huge value.

Use a signed index or restructure the loop.

Incorrect Counting Sort Range

Counting sort requires a count array large enough for every key.

If keys are in [0, k], the array size must be:

k + 1

A common bug is allocating only k.

For negative keys, shift by the minimum value:

index = value - min_value

Radix Sort Without Stability

Least-significant-digit radix sort requires a stable digit sort. If a digit pass is unstable, later passes can destroy the ordering created by earlier passes.

The digit sorter must preserve the relative order of elements with equal digit values.

Returning a Heap as Sorted Output

A heap is not a sorted array. It only guarantees the root is the minimum or maximum.

Incorrect assumption:

heap contents are sorted

Correct approach:

repeatedly extract root
or sort the heap contents

Mutating Input Unexpectedly

Quick sort, heap sort, and quickselect usually mutate the input. This can surprise callers that expect the original order to remain available.

Document mutation clearly, or copy the input before sorting.

Boundary Cases

Always test:

[]
[x]
[x, y]
all equal elements
already sorted input
reverse sorted input
many duplicate keys
large random input

Many sorting bugs appear only at these boundaries.

Debugging Strategy

When a sorting bug appears, check properties separately.

First check order:

output[i] <= output[i + 1]

Then check permutation:

frequency_map(input) == frequency_map(output)

Then check stability if required:

equal keys preserve original index order

This separation identifies whether the bug is in ordering, movement, or tie handling.

Takeaway

Most sorting bugs violate a small set of contracts: correct range bounds, comparator consistency, permutation preservation, order, and stability. Testing these properties independently makes failures easier to diagnose.