Sorting, stability, and a comparison lower bound

Prerequisites: Arrays, logarithms, permutations, and induction.

Learning objectives

• Prove a merge invariant.
• Explain stability and its dependence on tie handling.
• Derive the comparison-sorting lower bound and its scope.

Merge two ordered streams

Suppose left=[2a,4,7] and right=[2b,3,8], where the letters distinguish equal-valued records. Maintain indices i and j into the two arrays and an output prefix. The invariant is that the output contains exactly the consumed records in sorted order, and no unconsumed record is smaller than its final element. Choose the smaller next record, advancing only its stream. Once one stream ends, append the remainder of the other.

If equal keys choose the left stream first, the output is [2a,2b,3,4,7,8]. Assuming each child sort was stable and the left half preceded the right half in the input, this tie rule preserves original order among equal keys. Choosing the right item on equality still sorts by key but can destroy stability. Stability is a semantic requirement when earlier order carries meaning, such as arrival order within a priority class.

Derive merge sort’s resource bounds

Merging two arrays with total length n takes linear work: each iteration consumes a record, and there are only n records. Recursive balanced splitting yields T(n)=2T(n/2)+Theta(n), so worst-case comparison work is Theta(n log n). An ordinary array implementation uses linear auxiliary storage for merging. Reusing a buffer does not make that buffer disappear from the space accounting.

Insertion sort instead maintains a sorted prefix, placing each next record into it. Its worst case is quadratic because a reverse-ordered input shifts 1+2+…+(n−1) records. On already ordered input, a careful implementation can do linear comparison work. Which algorithm wins for tiny arrays depends on constants and locality, while the growth-rate distinction dominates at larger sizes.

Why comparisons cannot do asymptotically better in general

For n distinct keys, a comparison sort must distinguish n! possible input permutations. Model its comparisons as binary branches of a decision tree. A tree of height h has at most 2^h leaves, so 2^h≥n!, implying h≥log₂(n!). At least the largest n/2 factors of n! are at least n/2, giving log₂(n!)≥(n/2)log₂(n/2). Thus some input needs Omega(n log n) comparisons.

The conclusion is conditional on the comparison model. Counting sort or radix sort accesses bounded key representations directly and pays for their range or digit structure. They do not disprove the comparison lower bound. Similarly, known input order or restrictions can reduce the number of possible cases. To claim a sorting bound honestly, name the key model, required stability, memory budget, and whether the bound is worst-case or expected. MIT’s sorting notes give the formal development; reproduce the argument before treating the result as a slogan.

Practice problem

Merge left=[1a,3a,3b] and right=[1b,2,3c], preserving left-before-right ties. Show every choice. Then count the leaves required to distinguish all permutations of four distinct records and derive the minimum worst-case number of binary comparisons from that count. Explain why this lower bound does not rule out sorting four small integers by counting their frequencies.

Worked solution

The merge selects 1a,1b,2,3a,3b,3c. Equal values from the left half remain before corresponding values from the right half, while each half’s internal order is preserved. Four distinct records have 4!=24 permutations. A height-four binary tree has at most 16 leaves, insufficient to distinguish them; height five can have 32 leaves, so the lower bound is ceil(log₂24)=5 comparisons. Frequency counting is not limited to pairwise comparison outcomes: it uses integer values as indices and pays for initializing and scanning the key range. Different access models permit different bounds.

Check your understanding

Merge left=[(2,A),(4,B)] and right=[(2,C),(3,D)], where the left half appeared earlier originally. Which result is stable?

• [(2,A),(3,D),(2,C),(4,B)]
• [(2,A),(2,C),(3,D),(4,B)]
• [(2,A),(3,D),(4,B)]
• [(2,C),(2,A),(3,D),(4,B)]

Explanation

Equal key 2 records retain their original A-before-C order, and every record appears once in sorted order.

Keys are integers in 0..255, and counting sort takes O(n+256). Why does this not contradict the comparison-sorting lower bound?

• The lower bound assumes a linked-list representation.
• The lower bound applies only to already sorted input.
• Counting sort uses key values to index counts, exceeding the comparison-only model.
• Counting sort is secretly Ω(n log n) for this fixed range.

Explanation

The decision-tree lower bound constrains algorithms learning order only through comparisons; direct indexing exploits the restricted key representation.

Primary reading

• Introduction to Algorithms: lecture notes: MIT OpenCourseWare

Open the study and save your work →