beginnerintermediateadvanced

Algorithms · Sorting

Sorting Algorithms

How the classic sorts actually work, and the built-in tools that replace hand-rolling one in real code

Merge sortO(n log n) always, needs extra space
Quicksortin-place, but a bad pivot risks O(n²)
sorted() vs .sort()new list vs in-place, None return
key= over comparatorsone function call per element, not per pair

1.Merge sort — O(n log n), stable, extra space

Merge sort splits the array in half, recursively sorts each half, then merges the two now-sorted halves back together — the same two-pointer merge from Two Pointers, applied recursively.

Key features

O(n log n) in EVERY case (best, average, worst) — unlike quicksort, its performance does not depend on the input's arrangement
Needs O(n) extra space for the merged output at each level — it does not sort in place, unlike quicksort
Stable, but only if the merge step uses <= (not <) when comparing — see the mistake below

Merge sort is O(n log n) unconditionally, at the cost of O(n) extra space — and its comparison must use <=, not <, to actually keep the stability the algorithm is known for.

2.Quicksort — O(n log n) average, O(n²) worst case, in-place

Quicksort picks a pivot, partitions the array so everything smaller ends up on its left and everything bigger on its right, then recursively sorts each side — the pivot itself never needs to move again.

Key features

Average case O(n log n): a decent pivot roughly halves the array each time, giving log n levels of O(n) partitioning work
Worst case O(n²): a consistently bad pivot (like always the smallest or largest remaining value) shrinks the array by only one element per level, giving n levels instead of log n
In-place, unlike merge sort — a true implementation partitions within the same array using index swaps (see Partition Scheme), rather than building new lists as this teaching version does

Quicksort's O(n log n) average case depends entirely on the pivot roughly halving the array — a pivot chosen from a fixed position is exactly what an adversarial (or already-sorted) input can exploit to force O(n²).

3.`sorted()` and `list.sort()` — Timsort, stable, O(n log n)

sorted(iterable) builds and returns a brand-new sorted list, leaving the original untouched. list.sort() sorts a list in place and returns None. Mixing up which one returns what is the single most common sorting bug in Python.

Key features

Both use Timsort — O(n log n) worst case, stable, and optimized to detect and exploit already-sorted runs in real data
sorted() works on any iterable (a list, a string, a dict's keys, a generator) and always returns a list; .sort() only exists on list, and sorts it in place
.sort() returns None on purpose, the same convention as list.append() or list.reverse() — a method that mutates in place signals that by returning nothing

sorted() returns a new list and leaves the original alone; .sort() mutates in place and returns None — never write nums = nums.sort().

4.Insertion sort — good for nearly-sorted/small input

Insertion sort builds up a sorted prefix one element at a time, shifting each new value backward past every already-sorted value bigger than it — exactly how most people sort a hand of playing cards.

Key features

O(n²) worst case, but O(n) on already-sorted or nearly-sorted input — the inner while loop barely runs at all when little needs to move
Stable: a value only shifts past STRICTLY larger values, so two equal elements never swap relative order
This is what most standard-library sorts (including Timsort) fall back to for small subarrays, since its low overhead beats a fancier algorithm below some size threshold

Insertion sort is O(n²) worst case but close to O(n) on nearly-sorted input, since the inner loop only runs as far as something actually needs to move.

5.Partition scheme (Lomuto vs Hoare, conceptually)

Both partition schemes rearrange an array section in place so everything less than a pivot ends up before everything greater — Lomuto tracks one boundary while scanning left to right; Hoare closes two pointers in from both ends.

Key features

Lomuto always uses the LAST element as the pivot and returns its final index — simpler to write, but does about 3x more swaps than Hoare on average
Hoare's returned index is a split point, not necessarily the pivot's own final resting place — a common source of off-by-one bugs when adapting textbook Hoare code
Both run in O(n) per partition call — the difference between them is a constant-factor efficiency question, not a Big-O one

Both schemes partition in O(n) — Lomuto is simpler to write and returns the pivot's exact final index; Hoare does fewer swaps but its returned index is only a split point, not the pivot's position.

6.Counting sort — O(n + k), when values are bounded integers

Counting sort counts how many times each value appears, then reads the counts back out in value order — no comparisons between elements at all, so it can beat any comparison-based sort when values are bounded integers.

Key features

O(n + k) time and O(k) extra space, where n is the input size and k is the range of possible values — only fast when k is not much bigger than n
Every comparison-based sort has a proven Ω(n log n) floor — counting sort beats that only because it never compares two elements to each other at all
Falls apart on floats, strings, or a huge value range (like 32-bit integers) — the counts array itself would need one slot per possible value

Counting sort trades comparisons for counting — O(n + k) instead of O(n log n) — but only pays off when the value range k is small relative to n.

7.Stability of a sort, and when it matters

A stable sort never reorders two elements that compare equal on the sort key — sort by score alone, and everyone tied on score keeps whatever relative order they already had. An unstable sort makes no such promise.

Key features

Stability only matters when the sort key does NOT uniquely distinguish every element — sorting distinct numbers is unaffected either way, since nothing ever ties
Python's sorted() and list.sort() are guaranteed stable (Timsort) — this is a documented language guarantee, not an implementation accident
Sorting by multiple keys in one call (a tuple key) is usually simpler than relying on stability across two SEPARATE sorts, but both approaches work because of it

Stability only shows up when two elements tie on the sort key — a stable sort guarantees their original relative order survives, which is what makes sorting by multiple keys reliable.

8.`key=` parameter instead of writing custom comparators

key=fn tells sorted()/list.sort() to compare elements by fn(element) instead of the elements themselves — fn runs once per element, not once per pair compared.

Key features

key=len sorts by length; key=str.lower sorts case-insensitively; key=lambda x: x[1] sorts by a tuple's second element — the function just needs to return something COMPARABLE
The key function is called exactly once per element (O(n) calls total), not once per comparison (which would be O(n log n) calls)
Without key=, the elements themselves must already support the comparison being asked for — key= is what makes sorting objects by an ARBITRARY property possible

key=fn computes a comparison value once per element, up front — pass a function by name (len, str.lower) or a lambda for anything more specific.

9.Sorting by multiple criteria (`key=lambda x: (x[0], -x[1])`)

A tuple key sorts by its first element as the primary criterion, using the second (and further) elements only to break ties — exactly like a multi-column ORDER BY in a database query.

Key features

Every element of the key tuple after the first only ever gets consulted when everything before it tied — it never overrides the primary criterion
Negating a numeric field inside the tuple flips just THAT field to descending, while the rest of the tuple stays ascending — reverse=True on the whole call would flip everything
This generalizes to any number of criteria — key=lambda x: (x[0], -x[1], x[2]) sorts by three levels in one pass

A tuple key sorts left-to-right, tie-by-tie — negate a numeric field to flip only that ONE field to descending while the rest stay ascending.

10.`functools.cmp_to_key` for legacy comparator-style sorting

functools.cmp_to_key wraps an old-style comparator — a function taking two items and returning negative, zero, or positive — into something sorted()'s key= parameter can use, for logic that genuinely cannot be reduced to one value per element.

Key features

Needed specifically when the comparison depends on BOTH items together in a way no single per-element key value can capture
Slower than a plain key= function, since it calls the comparator once per comparison (O(n log n) calls) instead of once per element (O(n) calls) — reach for a real key first
Python 2's sorted(list, cmp=fn) comparator style was removed in Python 3 entirely — cmp_to_key is the bridge for porting that old logic forward

cmp_to_key is a bridge for comparator logic that genuinely needs both items at once — reach for a plain key= function first, since it is both simpler and faster.

Spotted a mistake on this page? Tell us.

Read Sheet