---
title: 'Choosing a Sorting Algorithm'
source: 'https://academia.sh/en/courses/algorithms/choosing-a-sorting-algorithm'
course: Algorithms
language: en
updated: '2026-08-17T18:07:41+00:00'
license: 'CC BY-SA 4.0'
---

# Choosing a Sorting Algorithm

A decision table based on data characteristics, the use of stability in multi-key sorting, hybrid implementations, and cases where sorting is unnecessary.

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.

```python
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.