Skip to content

6.1 Sorting Contracts

A sorting algorithm is correct only when its output is both ordered and a permutation of the input — two properties every implementation must preserve.

algorithms sorting correctness

Sorting begins with a contract. An algorithm is correct only if it satisfies two conditions: the output is ordered, and the output is a permutation of the input. Every implementation detail, optimization, and variation must preserve these two properties.

Problem

You are given a sequence A and a comparison relation ≤. You need a procedure that returns a sequence B such that B is ordered under ≤ and contains exactly the same elements as A.

Definitions

Let A = [a₁, a₂, ..., aₙ].

A sequence B = [b₁, b₂, ..., bₙ] is sorted if:

[ b_1 \le b_2 \le \cdots \le b_n ]

A sequence B is a permutation of A if every element appears the same number of times in both sequences.

Formally, for every value x:

[ \text{count}_A(x) = \text{count}_B(x) ]

Core Contract

A correct sorting algorithm must guarantee:

  1. Order condition For all i < j, B[i] ≤ B[j].

  2. Permutation condition B contains exactly the elements of A.

These conditions are independent. An algorithm may produce an ordered sequence that is not a permutation, or a permutation that is not ordered. Both failures must be excluded.

Stability

A sorting algorithm is stable if equal elements preserve their relative order.

Let a_i = a_j with i < j. After sorting, their positions p and q must satisfy p < q.

Stability matters when elements carry additional structure, such as records:

[(key=2, id=A), (key=1, id=B), (key=2, id=C)]

A stable sort ensures that records with equal keys remain in input order. This property allows multi-stage sorting, where you sort by secondary keys first and primary keys later.

Comparator Requirements

The comparison relation must behave consistently. In practice, it should define a strict weak ordering:

  • Transitive: if a ≤ b and b ≤ c, then a ≤ c
  • Antisymmetric in equality form
  • Total or at least consistent on comparable elements

If the comparator violates these properties, sorting may produce incorrect or undefined results. Many implementations assume comparator correctness and do not guard against violations.

Invariants

Most sorting algorithms maintain a partial ordering during execution. A typical invariant is:

  • A prefix is already sorted
  • The remaining suffix is unsorted

For example, insertion sort maintains:

[ A[1..k] \text{ is sorted at step } k ]

Correctness proofs reduce to showing:

  1. The invariant holds initially
  2. Each step preserves the invariant
  3. At termination, the invariant implies full sorting

Minimal Verification Strategy

To validate a sorting implementation:

  • Check ordering:

    for i in 1..n-1:
  assert B[i] ≤ B[i+1]

  • Check permutation: Compare frequency maps of A and B

Both checks are necessary. Ordering alone does not guarantee correctness.

Design Implications

The contract influences all design choices:

  • In-place algorithms must preserve permutation under mutation
  • Parallel algorithms must merge without losing elements
  • External sorting must maintain ordering across partitions
  • Stable algorithms must track relative positions

Any optimization that breaks the contract is invalid, regardless of performance gains.

Takeaway

Sorting is defined by two invariants: order and permutation. Stability is an additional constraint that affects algorithm choice. Every implementation should be reasoned about in terms of these properties before considering performance.