10.2 Sorting Comparison: From Constraints to Selection

Chapter 10 · Sorting Selection | Prerequisites: Basic Sorts, Merge Sort, Quick, Heap, and Non-Comparative Sorting | Next: Binary Search. This page no longer includes algorithm code, but instead organizes stability, worst-case performance, memory usage, key domain, and data distribution into auditable criteria for selection.

Before Writing Algorithms, Define Constraints

The actual conditions that shape decisions fall into five categories:

1. Whether stability is required, especially for multi-field sorting;
2. Whether you can tolerate expected performance, or whether worst-case time must be strictly bounded;
3. Whether available memory can accommodate an O(n) buffer;
4. Whether keys are range-controlled integers or can be decomposed into meaningful digit segments;
5. Whether input order, repetition rates, and distribution have been empirically measured.

Writing a fixed rule like "if n is less than 100, use insertion sort" is not an engineering conclusion. Thresholds depend on language, element size, comparator cost, hardware, and implementation, only target-environment benchmarks can determine them.

An Auditable Recommender

This function records candidates and reasons; it neither measures input nor sorts it. integer_range is max_key-min_key+1. The caller supplies counting_range_limit based on the current n, memory budget, and benchmarks; there is no built-in fixed cutoff. It also requires k <= n, a conservative condition that keeps the counting work linear. Wider ranges need separate evaluation. Without a limit, it does not recommend counting sort.

Here memory="tight" explicitly requires O(1) auxiliary space in the sorting core. worst_case="bounded" requests an O(n log n) worst-case bound instead of only an expected bound. These flags are not absolute millisecond or byte budgets, and do not remove the previous page's Θ(n) wrapper copies.

def recommend_sort(
    *,
    stable,
    integer_range,
    item_count=0,
    memory="normal",
    worst_case="expected",
    counting_range_limit=None,
):
    if not isinstance(stable, bool):
        raise TypeError("stable must be a boolean")
    if not isinstance(item_count, int):
        raise TypeError("item_count must be an integer")
    if item_count < 0:
        raise ValueError("item_count must be non-negative")
    for name, value in (("integer_range", integer_range),
                        ("counting_range_limit", counting_range_limit)):
        if value is not None:
            if not isinstance(value, int):
                raise TypeError(f"{name} must be an integer or None")
            if value < 1:
                raise ValueError(f"{name} must be positive")
    if memory not in {"normal", "tight"}:
        raise ValueError("memory must be 'normal' or 'tight'")
    if worst_case not in {"expected", "bounded"}:
        raise ValueError("worst_case must be 'expected' or 'bounded'")
    if item_count == 0:
        return {"algorithm": "no sort", "reasons": ["input is empty"]}

    if (integer_range is not None and counting_range_limit is not None
            and integer_range <= counting_range_limit
            and integer_range <= item_count and memory == "normal"):
        return {
            "algorithm": "counting sort",
            "reasons": [
                "integer keys have a measured range",
                "the range fits the caller's explicit counting-sort limit",
            ],
        }
    if memory == "tight":
        if stable:
            raise ValueError(
                "this shortlist has no stable O(1)-auxiliary sort with an "
                "O(n log n) bound; review algorithms or relax a constraint"
            )
        return {
            "algorithm": "heapsort",
            "reasons": [
                "textbook auxiliary space is O(1)",
                "worst-case time is Θ(n log n)",
            ],
        }
    if stable:
        return {
            "algorithm": ("stable library sort with a documented worst-case bound"
                          if worst_case == "bounded" else "stable library sort"),
            "reasons": [
                "stability is required",
                "verify the requested time bound in the selected library",
            ],
        }
    if worst_case == "bounded":
        return {
            "algorithm": "library sort with a documented worst-case bound",
            "reasons": [
                "stability is not required",
                "the deployment requires a worst-case guarantee",
            ],
        }
    return {
        "algorithm": "library sort; benchmark against randomized quicksort",
        "reasons": [
            "expected time is acceptable",
            "no budgeted integer-domain advantage was established",
        ],
    }

For example, suppose measurement has established a counting-range limit of 1024 for the current 100,000 records:

choice = recommend_sort(
    stable=True, integer_range=101, item_count=100_000,
    worst_case="bounded", counting_range_limit=1024,
)
assert choice["algorithm"] == "counting sort"
choice = recommend_sort(
    stable=False, integer_range=None, item_count=100_000,
    memory="tight", worst_case="expected",
)
assert choice["algorithm"] == "heapsort"

The second call still selects heapsort. Accepting expected time does not make recursive quicksort's O(log n) stack satisfy a strict O(1) space requirement.

Guarantee Matrix

Algorithm	Best/Expected/Worst Time	Stable	Textbook Algorithm Auxiliary Space	Failure Conditions
Insertion	Θ(n) / Θ(n²) / Θ(n²)	Yes	O(1)	Large number of inversions results in high movement cost
Merge	Θ(n log n) / same / same	Yes	O(n)	Memory budget insufficient for buffer allocation
Random Three-Way Quick Sort	Expected O(n log n), worst-case O(n²)	No	Previous implementation: worst-case O(log n) stack	Worst-case degradation not allowed or stability required
Heap Sort	Worst-case Θ(n log n), heap construction Θ(n)	No	O(1)	Stable output is required
Counting	Θ(n + k)	Can be stable	Θ(n + k)	k is much larger than n
LSD Radix Sort	Θ(d(n + b))	Stable if each pass is stable	Θ(n + b)	Keys cannot be reliably decomposed into finite digits
Bucket	Expected O(n+m+n²/m) under uniform assignment; worst O(n²+m)	Depends on bucket algorithm	Θ(n + m)	Data distribution skewed, bucket load concentrated

Insertion-sort expectation assumes uniformly random permutations of distinct keys; merge sort refers to the fixed-split version above. Radix-sort d is at least 1. Bucket count m contributes to time; linear expectation requires suitable loads and m=Θ(n). Space excludes the unified API's Θ(n) auxiliary records and Θ(n) output list. A worst-case Θ(n log n) bound does not mean every input takes that much work.

Three Common Misjudgments

Small-range integers

A dataset of 100,000 scores ranging from 0 to 100 has a key-range size of 101. When memory is available and stability is required, counting sort offers a clear data-domain advantage. However, if there are just ten records spanning a 64-bit key space, counting sort no longer offers that advantage.

Memory-constrained but stability required

Treating heap sort as the inevitable solution overlooks the conflict between stability and memory efficiency. Standard heap sort is inherently unstable. Stable insertion sort uses O(1) auxiliary space but has Θ(n²) worst-case time. The remaining question is whether O(n log n) is required too. This page's shortlist contains no algorithm meeting all three requirements; its exception is a limitation of the shortlist, not an impossibility proof. More complex in-place stable merging algorithms need separate evaluation. External sorting and stream redesign become relevant when the data itself does not fit in memory.

Approximately uniform distribution

The linear expected performance of bucket sort stems from a distribution model. Inspect a histogram, the maximum bucket load, and the bucket count relative to n. Without actual measurement, "uniformity" remains just a hope.

Standard Library Boundaries

Prioritize the standard library. The Python documentation guarantees stability and explicitly states that each element's key is invoked only once. Similarly, the Java SE 25 Arrays.sort(Object[]) documentation provides stability assurances. The specific choice of hybrid sorting algorithm is typically documented as a versioned implementation note, behavior may change in future versions, so it's essential to reverify upon upgrades. Never infer permanent behavior from the name of an older implementation.

Sources:

• Python Sorting HOWTO
• Java SE 25 Arrays
• Princeton quicksort
• Princeton heapsort
• Princeton radix sorts

Recheck the Constraints When Inputs Change

Choosing a sorting algorithm isn't about memorizing "fastest"; it's about leaving traceable justification: where did the key domain come from? Who enforces stability? Why is the worst-case bound necessary? What's the memory budget? On which target environment was the baseline benchmark run? When constraints change, reevaluate the choice. General-purpose libraries are typically the first baseline; specialized algorithms must trade narrower input contracts for performance gains.

Review the previous section at Chapter 10: Sorting Implementations. The next chapter covers Binary Search and Boundary Finding.