# 6.24 Common Bugs

# 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:

```text id="y6tj0r"
[lo, hi)
```

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

```text id="cwq1gm"
hi - lo
```

The base case is usually:

```text id="uskcbz"
if hi - lo <= 1:
  return
```

A common bug is mixing this with a closed interval:

```text id="q05gun"
[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:

```text id="nabhna"
quick_sort(A, lo, p)
quick_sort(A, p + 1, hi)
```

A common incorrect version is:

```text id="seq61n"
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:

```text id="d7swmn"
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:

```text id="b897m6"
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:

```text id="ogj3ee"
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:

```text id="j9nf91"
return a - b
```

This can overflow. Use explicit comparison instead:

```text id="qwr0ba"
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:

```text id="e4jaow"
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:

```text id="zdlw78"
sift_down(A, 0, end)
```

not:

```text id="xpagh3"
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:

```text id="dmh1kk"
mid = (lo + hi) / 2
```

Safer midpoint:

```text id="ldy33f"
mid = lo + (hi - lo) / 2
```

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

```text id="edmixu"
n(n - 1) / 2
```

## Unsigned Index Underflow

Insertion sort often decrements an index below zero.

Bug-prone pattern:

```text id="s8g89f"
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:

```text id="16mzso"
k + 1
```

A common bug is allocating only `k`.

For negative keys, shift by the minimum value:

```text id="cj2nbp"
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:

```text id="lbzrzr"
heap contents are sorted
```

Correct approach:

```text id="ga1m9f"
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:

```text id="bo8cpc"
[]
[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:

```text id="1a4wqv"
output[i] <= output[i + 1]
```

Then check permutation:

```text id="khu9qy"
frequency_map(input) == frequency_map(output)
```

Then check stability if required:

```text id="8qwsvw"
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.