Choosing a Sorting Algorithm

Seven algorithms and six distinct criteria have accumulated. This lesson gathers them into a single decision framework. The goal is not to memorize a list of sorts, but to see which property of the data at hand determines the choice.

A Combined View of the Criteria

Algorithm	Worst	Average	Extra space	Stable	Adaptive
Insertion	$O(n^2)$	$O(n^2)$	$O(1)$	Yes	Yes
Selection	$O(n^2)$	$O(n^2)$	$O(1)$	No	No
Bubble	$O(n^2)$	$O(n^2)$	$O(1)$	Yes	Yes
Merge	$O(n \log n)$	$O(n \log n)$	$O(n)$	Yes	Depends on variant
Quick	$O(n^2)$	$O(n \log n)$	$O(\log n)$	No	No
Heap	$O(n \log n)$	$O(n \log n)$	$O(1)$	No	No
Counting	$O(n + k)$	$O(n + k)$	$O(n + k)$	Yes	No
Radix	$O(d(n + b))$	$O(d(n + b))$	$O(n + b)$	Yes	No

The table alone does not decide; the problem determines which column matters.

The Decision Table

Property of the data	Suitable choice	Rationale
Few elements (tens)	Insertion	Small constant, simple code
Nearly sorted	Insertion or run-based merge	Low inversion count
Stability required	Merge, counting, radix	Stable by definition
Very tight memory	Heap	$O(1)$ extra space, has a guarantee
Worst-case guarantee needed	Heap or merge	Does not fall into the quadratic case
General-purpose, on an array	Hybrid (quick + heap + insertion)	Practical speed and a guarantee
Linked list	Merge	Sequential access is enough
Data that does not fit in memory	External merge	Reads as a stream
Keys are small integers	Counting	$O(n + k)$, no comparison
Fixed-width key, many records	Radix	Linear per digit
Many repeated keys	Three-way quicksort	The equal region is never reprocessed
Only the largest $k$ elements	Heap of size $k$	$O(n \log k)$, no sorting needed

Most of the rows are not mutually exclusive; if more than one condition holds, the more restrictive one decides. If “stability required” clashes with “tight memory”, a stable, in-place algorithm is sought — implementations that give both exist, but their constants are large.

Hybrid Implementations

General-purpose library sorts do not use a single algorithm. Two common designs exist, and both are assembled from this topic’s lessons.

Partition-based hybrid. It starts with quicksort. If recursion depth exceeds the $c \log n$ threshold — meaning the splits keep being unbalanced — it switches to heap sort. Segments below a certain size are left to insertion sort. The result: quicksort’s practical speed, heap sort’s worst-case guarantee, insertion sort’s small constant.

Run-based hybrid. The runs already sorted in the input are found, short runs are extended with insertion sort, and the runs are then merged. It approaches linear on nearly sorted data, is stable, and stays $O(n \log n)$ in the worst case. In exchange, it requires extra space.

The shared lesson: real implementations do not claim any single algorithm is best; they use each algorithm in the region where it excels.

Multi-Key Sorting

Stability’s most common use is sorting by more than one criterion. There are two routes.

Composite key. The comparison function evaluates the criteria in order. It finishes in a single pass and does not require stability.

Successive stable sorts. Sorting is done first by the secondary criterion, then by the primary one. Because the second sort is stable, the secondary order of elements equal on the primary criterion is preserved.

records = [
    ("Ankara", 3), ("Izmir", 1), ("Ankara", 1),
    ("Bursa", 2), ("Izmir", 3), ("Ankara", 2),
]

# Secondary criterion (number) first, primary criterion (city) second
step1 = sorted(records, key=lambda k: k[1])
step2 = sorted(step1, key=lambda k: k[0])
print(step2)
# [('Ankara', 1), ('Ankara', 2), ('Ankara', 3), ('Bursa', 2), ('Izmir', 1), ('Izmir', 3)]

# Single pass with a composite key — same result
print(sorted(records, key=lambda k: (k[0], k[1])) == step2)     # True

Both routes give the same result. The successive method is more flexible when the criteria are determined at run time (a table sorted by the column the user picks); the composite key is cheaper because it is a single pass.

Radix sort’s digit-by-digit operation follows the same principle: every digit is a criterion, and stability preserves the result of the previous criteria.

Comparison Cost

Asymptotic tables count comparison as constant. If the key is complex, this assumption breaks: comparing long strings is proportional to string length, and locale-sensitive sorting rules are far more expensive.

Two consequences follow. First, if comparison is expensive, the algorithm that reduces the number of comparisons (merge) is preferred; if moving is expensive, the one that reduces moves (selection). Second, an expensive key transformation can be done once, before sorting, and cached — not recomputed on every comparison throughout the sort. This is a direct application of the precomputation pattern from the Time and Space Trade-off lesson.

Cases Where Sorting Is Unnecessary

Sorting is an operation that does more than what is needed, and it is often called unnecessarily.

Need	Instead of sorting	Cost
The largest or smallest element	A single scan	$O(n)$
The kth smallest element	Quickselect	Expected $O(n)$
The largest $k$ elements	A heap of size $k$	$O(n \log k)$
Whether a value exists	A hash table	Expected $O(1)$
Filtering out duplicates	A hash set	Expected $O(n)$
The median value	A selection algorithm	Expected $O(n)$

If sorting itself is genuinely needed — presenting output in order, preparing for binary search, many-query use — its cost is warranted. Sorting to answer a single question means paying $O(n \log n)$ to do work that is $O(n)$.

The Point Where Measurement Decides

Asymptotic analysis determines the class; choosing within a class requires measurement. If two algorithms are both $O(n \log n)$, the difference lies in the constant, and the constant depends on memory access pattern, key type, data size, and implementation.

Three rules apply when measuring: it should be measured with real data (random data does not carry the partial ordering of real data), it should be measured with the input size varied (a single size does not reveal the class), and how the measured durations scale with the input should be examined — the scale-growth table from the Reading Complexity Classes lesson is for exactly this job.

Summary

• The choice comes from the data’s properties, not from the algorithm itself: size, partial ordering, the proportion of repeated keys, key structure, memory constraint, and the stability requirement.
• General-purpose implementations are hybrids; they use each algorithm in the region where it excels.
• Multi-key sorting is done with successive stable sorts or with a composite key.
• If comparison is expensive, the algorithm that reduces comparisons is chosen; if moving is expensive, the one that reduces moves.
• Sorting is unnecessary for minimum, kth, first-$k$, or existence questions; linear or expected-constant-cost solutions exist.
• The decision within a class is given by measurement; measurement is done with real data and at more than one input size.

Next Step

Searching and sorting have worked on one-dimensional data: elements had only an ordering relation between them. The next topic moves to data where elements have connections. The Data Structures course defined graphs and built breadth-first and depth-first search; now the problems of shortest path, minimum spanning tree, and maximum flow in weighted graphs will be covered.