10.1 Quick, Heap, and Non-Comparison Sorts
Chapter 10 · Implementing Sorting Algorithms | Prerequisites: Basic Sorting, Merge Sort, and Binary Heap | Next: Sorting Algorithm Selection. This lesson implements randomized three-way quicksort, heap sort, counting sort, radix sort, and bucket sort, and derives the lower bound for comparison-based sorting.
Constraints for the Second Group of Sorting Algorithms
No single algorithm dominates all cases. Quick sort relies on pivot-based partitioning, and its performance hinges on whether the partitioning is balanced; heapsort provides a worst-case time bound and an in-place core; counting, radix, and bucket sorts avoid the lower bound of comparison-based sorting but require additional knowledge about the data domain. The mathematical question of this chapter is: what speed limits does the act of comparison itself impose?
First, Agree on the Interface
The following five functions accept any iterable object and an optional key, returning a new list without modifying the caller's input. Each element's key is computed exactly once. To achieve this, the public wrapper layer copies and decorates n records, using Θ(n) auxiliary records and a separate Θ(n) output list. Input iterators are consumed, and element objects remain shared by reference. Original positions record identity but do not break ties or guarantee stability. Quicksort and heapsort require a consistent < ordering, excluding NaN. Costs below treat key extraction, comparisons, and integer arithmetic as constant-time; arbitrary-precision integers add bit-length costs. The term "algorithm auxiliary space" that appears later refers strictly to the core algorithmic process described in textbooks, excluding the overhead of this unified interface.
import random
from math import isfinite
def _decorate(values, key):
key_fn = key if key is not None else lambda item: item
return [[key_fn(item), index, item] for index, item in enumerate(values)]
def _values(records):
return [record[2] for record in records]
def quick_sort(values, key=None, rng=None):
records = _decorate(values, key)
generator = rng if rng is not None else random
def sort_range(low, high):
while low < high:
pivot = records[generator.randrange(low, high + 1)][0]
less = low
scan = low
greater = high
while scan <= greater:
if records[scan][0] < pivot:
records[less], records[scan] = records[scan], records[less]
less += 1
scan += 1
elif pivot < records[scan][0]:
records[scan], records[greater] = records[greater], records[scan]
greater -= 1
else:
scan += 1
if less - low < high - greater:
sort_range(low, less - 1)
low = greater + 1
else:
sort_range(greater + 1, high)
high = less - 1
sort_range(0, len(records) - 1)
return _values(records)
def heap_sort(values, key=None):
records = _decorate(values, key)
def sift_down(root, size):
while 2 * root + 1 < size:
child = 2 * root + 1
if child + 1 < size and records[child][0] < records[child + 1][0]:
child += 1
if not records[root][0] < records[child][0]:
return
records[root], records[child] = records[child], records[root]
root = child
for root in range(len(records) // 2 - 1, -1, -1):
sift_down(root, len(records))
for end in range(len(records) - 1, 0, -1):
records[0], records[end] = records[end], records[0]
sift_down(0, end)
return _values(records)
def counting_sort(values, key=None):
records = _decorate(values, key)
if not records:
return []
if any(not isinstance(record[0], int) for record in records):
raise TypeError("counting_sort requires integer keys")
minimum = min(record[0] for record in records)
maximum = max(record[0] for record in records)
counts = [0] * (maximum - minimum + 1)
for record in records:
counts[record[0] - minimum] += 1
for index in range(1, len(counts)):
counts[index] += counts[index - 1]
output = [None] * len(records)
for record in reversed(records):
slot = record[0] - minimum
counts[slot] -= 1
output[counts[slot]] = record
return _values(output)
def radix_sort(values, key=None):
records = _decorate(values, key)
if not records:
return []
if any(not isinstance(record[0], int) for record in records):
raise TypeError("radix_sort requires integer keys")
offset = min(record[0] for record in records)
largest = max(record[0] - offset for record in records)
place = 1
while place <= largest or place == 1:
counts = [0] * 10
for record in records:
digit = ((record[0] - offset) // place) % 10
counts[digit] += 1
for index in range(1, 10):
counts[index] += counts[index - 1]
output = [None] * len(records)
for record in reversed(records):
digit = ((record[0] - offset) // place) % 10
counts[digit] -= 1
output[counts[digit]] = record
records = output
place *= 10
return _values(records)
def bucket_sort(values, key=None, bucket_count=None):
records = _decorate(values, key)
count = max(1, len(records)) if bucket_count is None else bucket_count
if not isinstance(count, int) or count < 1:
raise ValueError("bucket_count must be a positive integer")
if not records:
return []
if any(not isinstance(record[0], (int, float)) for record in records):
raise TypeError("bucket_sort requires int or float keys")
if any(isinstance(record[0], float) and not isfinite(record[0])
for record in records):
raise ValueError("bucket_sort requires finite keys")
minimum = min(record[0] for record in records)
maximum = max(record[0] for record in records)
if minimum == maximum:
return _values(records)
integer_keys = all(isinstance(record[0], int) for record in records)
if integer_keys:
span = maximum - minimum + 1
else:
try:
span = maximum - minimum
if not isfinite(span):
raise ValueError("floating-point key span must be finite")
except OverflowError as exc:
raise ValueError("floating-point key span is too large") from exc
buckets = [[] for _ in range(count)]
for record in records:
if integer_keys:
index = (record[0] - minimum) * count // span
else:
index = min(count - 1, int((record[0] - minimum) / span * count))
buckets[index].append(record)
for bucket in buckets:
for index in range(1, len(bucket)):
record = bucket[index]
scan = index - 1
while scan >= 0 and record[0] < bucket[scan][0]:
bucket[scan + 1] = bucket[scan]
scan -= 1
bucket[scan + 1] = record
return _values([record for bucket in buckets for record in bucket])After copying the definitions above, check the results with labeled records:
data = [(3, "a"), (-1, "x"), (3, "b"), (0, "y")]
for algorithm in (quick_sort, heap_sort, counting_sort, radix_sort, bucket_sort):
result = algorithm(data, key=lambda item: item[0])
assert [item[0] for item in result] == [-1, 0, 3, 3]
for algorithm in (counting_sort, radix_sort, bucket_sort):
assert algorithm(data, key=lambda item: item[0]) == [
(-1, "x"), (0, "y"), (3, "a"), (3, "b")
]
assert data == [(3, "a"), (-1, "x"), (3, "b"), (0, "y")]Quicksort: A Pivot Is Not a Guarantee
For [4, 2, 4, 1, 4, 3] choose pivot 4, the completed partition groups values into three regions; order within a region may differ:
< 4: [2, 1, 3] == 4: [4, 4, 4] > 4: []The equal region is excluded from recursive processing, so large numbers of duplicate keys won't result in a long chain of ineffective partitions. Random pivot selection keeps the recursion tree reasonably balanced on fixed inputs, yielding an expected time complexity of O(n log n); however, if successive pivots consistently choose extreme values, subproblems of size n, n−1, n−2 may still arise, leading to a worst-case O(n²) performance. Three-way partitioning improves handling of duplicate keys, but it cannot eliminate the worst-case scenario entirely.
During partitioning, [low, less) contains smaller keys, [less, scan) equal keys, [scan, greater] unchecked keys, and (greater, high] larger keys. A value swapped in from the right is still unchecked, so that branch decreases greater without advancing scan. All-equal input takes one linear pass.
The expected bound assumes uniform pivot selection within the current range and input fixed independently of those choices. rng=random.Random(fixed_seed) reproduces a run; a fixed seed does not guarantee fast execution on a particular input. Recursing on the shorter side and looping over the longer side at least halves the size at every recursive level, so even worst-case stack depth is O(log n). Swaps cross over equal elements, so this version of quicksort is unstable.
Heap Sort: First Convert the Array into a Heap
Using [12, 11, 13, 5, 6, 7] as an example, we sink down from the last non-leaf node at index 2:
root 2: 13 is already greater than its children 7
root 1: 11 is already greater than 5 and 6
root 0: 12 swaps with the larger child 13
Result: [13, 11, 12, 5, 6, 7]Then swap the root (13) with the last element, shrink the heap, and sink from the root again. Each iteration extracts the current maximum value, and the sorted region grows from right to left.
Why is heap construction Θ(n), not Θ(n log n)? Most nodes are near the leaves and can only sink a few levels. Summing the maximum sinking depth for each node yields a linear total. The sorting phase performs n−1 sink operations, each taking at most O(log n) time, giving worst-case total time Θ(n log n). Summing per-sift upper bounds directly proves only O(n log n), not that every input takes that long. This implementation takes Θ(n) on all-equal input. Textbook array-based heap sort algorithms use O(1) auxiliary space, but the unified "no input modification + single key computation" wrapper on this page still consumes O(n) space. Heap sort is unstable.
Counting Sort: Ranges Also Come with Cost
The smallest key in [-2, 1, -2, 0] is -2 and the largest is 1, giving an inclusive range of k = 4. The slots in the counting array from 0 to 3 correspond to the values -2 through 1. Prefix sums determine the ending positions for each key, and reversing the write-back preserves the original order of equal elements.
Time complexity: Θ(n + k), auxiliary space: Θ(n + k). When n is only a thousand but the keys span the entire 64-bit integer range, k becomes the real bottleneck; counting sort should not be used in such cases. This example allocates directly from k and has no memory-budget guard; check the range before using it on real input.
Radix Sort: Every Digit Must Be Stable
This implementation first subtracts the minimum key, aligning negative numbers and shifted non-negative values onto the same ordered axis. For example, [-12, 3, -1] is shifted to [0, 15, 11]. We first perform a stable sort on the units digit, then on the tens digit, and ultimately recover the original integer order.
Here b=10, with digits processed from least to most significant: LSD radix sort. Let d be the number of decimal digits in the largest shifted key. All-equal input counts as one digit and performs one distribution pass. Time is Θ(d(n+b)) and extra space Θ(n+b). Each stable pass preserves the ordering established by lower digits; an unstable pass can break the final result.
Bucket Sort: The Average Bound Comes from Distribution Assumptions
Bucket sort maps the numeric range into m buckets and uses stable insertion sort within each. With n_i elements in bucket i, time is bounded by O(n+m+Σ n_i²). Under independent uniform bucket assignment, the expected squared-load sum is n+n(n-1)/m, giving expected O(n+m+n²/m) time. Linear expectation needs controlled loads, for example m=Θ(n); m≈√n can still take Θ(n^(3/2)). This implementation defaults to m=n and also accepts an explicit count. MIT's bucket-sort lecture develops the bucket-load analysis.
Keys must be integers or finite floats. All-integer input uses integer division for bucket assignment, avoiding conversion of large integers to floats. The floating-point branch also requires a finite representable span and clamps the maximum endpoint to the last bucket. All-equal input returns immediately, so it is not a quadratic case. To exercise the worst case, put many distinct decreasing values in one bucket, for example with bucket_count=1. For arbitrary m, the worst-case upper bound is O(n²+m); writing just O(n²) assumes m=O(n²).
Mathematical Challenge: Lower Bound on Comparison Sorting
With n distinct elements, there are n! possible permutations. When considering only binary comparisons, a deterministic comparison sort can be represented as a decision tree: internal nodes represent a single comparison, and leaves represent the final sorted order. The tree must contain at least n! leaves, so the length of the longest path satisfies:
Thus, the worst-case number of comparisons required by any comparison sort is at least Ω(n log n). Counting sort and radix sort can surpass this bound because they leverage the full range of integer keys or digit values, avoiding reliance solely on pairwise comparisons. The lower bound remains intact, but the computational model has changed.
Professional Reference
| Algorithm | Time | Stable | Textbook Algorithm Auxiliary Space | Check First |
|---|---|---|---|---|
| Randomized Three-Way Quick Sort | Expected O(n log n), worst-case O(n²) | No | Controlled recursion O(log n) | Are unstable outputs acceptable? Do adversarial inputs exist? |
| Heap Sort | Worst-case Θ(n log n), heap construction Θ(n) | No | O(1) | Is a worst-case guarantee required? Is in-place operation necessary? |
| Counting Sort | Θ(n + k) | Yes | Θ(n + k) | Is k comparable in scale to n? |
| LSD Radix Sort | Θ(d(n + b)) | Yes | Θ(n + b) | Can keys be decomposed into a finite number of digits? |
| Bucket Sort | Expected O(n+m+n²/m) under uniform assignment; worst O(n²+m) | Stable in this implementation | Θ(n + m) | Can the distribution assumption be measured? |
Engineering Boundaries
Production code should prioritize using the language standard library, and only implement custom solutions when specific requirements or constraints necessitate it. The Python documentation guarantees stable sorting, indicating that key each record is computed once and that the implementation leverages the existing order. In contrast, the Java SE 25 documentation guarantees stable sorting for object arrays, but specifies the implementation details as an implementation note, meaning those details may change across versions and should not be treated as permanent language rules.
References:
Check Sorting Boundaries
- Generate a three-way partition of
[3, 5, 3, 1, 3, 2]using a fixed random seed. - Manually simulate heap construction for seven elements, documenting each sink operation.
- Set an upper bound on
k/nfor counting sort and explain why this bound should be determined by memory constraints. - Set
bucket_count=1for distinct decreasing keys and trace insertion sort within the bucket. Compare this with the immediate return for all-equal input.
General-purpose sorting handles unknown data distributions, while counting, radix, and bucket sorts trade off performance for narrower key ranges or assumed data distributions. Randomization in quicksort provides expected-case guarantees, while heapsort offers worst-case bounds and in-place operation, these assurances are not interchangeable.
After completing the manual calculations, go to Sorting Selection and place stability, memory usage, and input distribution into a unified decision matrix.