Sorting Algorithms

How the main sorting algorithms work, what each one costs, and how to use a built-in sort with a custom key. In practice, sorting is most often the first step that makes the real algorithm simple.

Overview

Why sorting matters

You will rarely be asked to write a sort from scratch. You will often sort first, because sorted data has structure that other techniques rely on. The sort costs O(n log n), and the step after it is often a single O(n) pass.

Equal values sit next to each other — find duplicates and group items in one pass — Contains Duplicate, Group Anagrams
Values are in order — use binary search or two pointers — Three Sum, Find K Closest Elements
Intervals are ordered by start — merge or check overlaps in one pass — Merge Intervals, Meeting Rooms
Items are ranked by a greedy key — take the best item first — Non-overlapping Intervals, Car Fleet

What to know: when sorting helps, what it costs, whether it loses information you need (such as the original indexes), and how to write the comparison.

The main algorithms at a glance

Insertion sort — O(n) — O(n²) — O(n²) — O(1) — yes
Merge sort — O(n log n) — O(n log n) — O(n log n) — O(n) for arrays — yes
Quicksort — O(n log n) — O(n log n) — O(n²) — O(log n) stack if you recurse on the smaller side — no
Heapsort — O(n log n) — O(n log n) — O(n log n) — O(1) — no
Counting sort — O(n + k) — O(n + k) — O(n + k) — O(n + k) — yes, when written to be
Radix sort (LSD) — O(d(n + k)) — O(d(n + k)) — O(d(n + k)) — O(n + k) — yes

Here k is the range of key values (or the digit base in radix sort) and d is the number of digits. A sort is stable when items with equal keys keep their original order.

Merge sort: split, then merge

Merge sort splits the array in half, sorts each half, then merges the two sorted halves. The merge is where the work happens: look at the front of each half and take the smaller one.

The trace below merges [2, 5, 7] with [1, 4, 9].

1 — 2 — 1 — 1 from the right — 1
2 — 2 — 4 — 2 from the left — 1 2
3 — 5 — 4 — 4 from the right — 1 2 4
4 — 5 — 9 — 5 from the left — 1 2 4 5
5 — 7 — 9 — 7 from the left — 1 2 4 5 7
6 — empty — 9 — copy the rest — 1 2 4 5 7 9

On a tie, taking from the left half keeps equal items in order, which is what makes merge sort stable. On a linked list the merge needs no extra array, which is why merge sort is the usual answer for Sort List.

Quicksort: partition around a pivot

Quicksort picks a pivot, moves smaller values to its left and larger values to its right, and then sorts the two sides. After one partition the pivot is in its final place.

The trace below partitions [7, 2, 9, 4, 5] with the last value, 5, as the pivot. i starts at -1.

0 — 7 — leave — -1 — 7 2 9 4 5
1 — 2 — swap a[0] and a[1] — 0 — 2 7 9 4 5
2 — 9 — leave — 0 — 2 7 9 4 5
3 — 4 — swap a[1] and a[3] — 1 — 2 4 9 7 5
end — swap pivot into index 2 — 2 4 5 7 9

The worst case is O(n²): when every pivot is the smallest or largest value, each partition removes only one item. A fixed last-element pivot does exactly that on sorted input. A random pivot makes this very unlikely, and the expected time is O(n log n).

Why O(n log n) is the floor for comparison sorts

A comparison sort learns about the input only by asking 'is a before b?'. Picture every run of the algorithm as a binary tree of questions. Each of the n! possible orders must end at its own leaf, and a binary tree of height h has at most 2^h leaves. So the worst case needs at least log2(n!) comparisons, which grows like n log2 n.

10 — about 22 — about 33 — 100
100 — about 525 — about 664 — 10,000
1,000 — about 8,529 — about 9,966 — 1,000,000

Counting and radix sort escape this bound because they never compare two items. They read the key's value and use it as an index.

Beating the floor: counting sort and radix sort

Counting sort works on small integer keys. Count how often each value appears, then write the values out in order. The trace below sorts [3, 1, 4, 1, 0, 3], whose values are between 0 and 4.

Count — 1 — 2 — 0 — 2 — 1

Reading the counts in order gives [0, 1, 1, 3, 3, 4]. The cost is O(n + k) for n items and k possible values, so it pays off only when k is not much larger than n.

Radix sort (least significant digit first) runs a stable sort on one digit at a time, from the last digit to the first. Stability is what keeps the work of earlier passes.

start — 170 45 75 90 802 24 2 66
1 — ones digit — 170 90 802 2 24 45 75 66
2 — tens digit — 802 2 24 45 66 170 75 90
3 — hundreds digit — 2 24 45 66 75 90 170 802

Stability and sorting by several keys

Stability matters when you sort by one key and want an earlier order to survive among ties. Sorting [(a, 2), (b, 1), (c, 2)] by the number shows the difference.

Stable — (b, 1) (a, 2) (c, 2) — a was before c, and stays before c
Unstable (allowed) — (b, 1) (c, 2) (a, 2) — ties may come out in any order

With a stable sort you can sort by the minor key first and the major key second. Most of the time it is simpler to sort once with a tuple key, such as key=lambda p: (p.last, p.first).

What your language's built-in sort does

Python — sorted(xs), xs.sort() — Timsort, an adaptive merge sort that finds runs already in order — yes, guaranteed
Java, primitives — Arrays.sort(int[]) — Dual-Pivot Quicksort (Yaroslavskiy, Bentley, Bloch) — not needed: equal ints are the same
Java, objects — Arrays.sort(T[], cmp), List.sort — adaptive iterative merge sort adapted from Python's Timsort — yes, guaranteed
JavaScript — arr.sort(cmp) — left to the engine — yes, since ECMAScript 2019

> [!WARNING] > JavaScript's sort() with no comparator converts values to strings. [1, 30, 4, 100000].sort() gives [1, 100000, 30, 4]. Pass (a, b) => a - b for numbers.

Custom comparators

A comparator says which of two items goes first. Python prefers a key function, which is called once per item. When the order truly depends on both items, wrap a two-argument function with functools.cmp_to_key.

Largest Number is the classic case. To decide whether 3 goes before 30, compare the two ways of joining them as strings: 330 is bigger than 303, so 3 goes first.

3 — 30 — 330 — 303 — 3
34 — 3 — 343 — 334 — 34
9 — 5 — 95 — 59 — 9

Sorting [3, 30, 34, 5, 9] this way gives 9, 5, 34, 3, 30, so the answer is 9534330.

In Java, a comparator written as a - b can overflow. With a = -2,147,483,648 and b = 1, the subtraction wraps around to a large positive number, so the comparator says a is bigger. Use Integer.compare(a, b) instead.

Quickselect: the k-th value without a full sort

To find the k-th smallest value you only need the pivot in the right place, not the whole array in order. Partition once, then continue only on the side that holds index k.

Sort, then index — O(n log n) — depends on the sort — simplest to write
Min-heap of size k — O(n log k) — O(k) — works on a stream
Quickselect, random pivot — O(n) expected, O(n²) worst — O(1) if written as a loop — changes the array

What you will be able to do

Say when sorting first makes a problem simple, and what it costs.
Explain merge sort, quicksort and the O(n log n) lower bound for comparison sorts.
Pick counting or radix sort when keys are small integers.
Write a correct custom comparator in Python, Java and JavaScript.
Find the k-th smallest value with quickselect, and compare it with a heap.

When to use it

Before binary search or two pointers, which need sorted input
Interval problems: sort by start to merge, by end to schedule
Grouping equal or related items so they sit next to each other
Custom orders, such as Largest Number or Reorder Data in Log Files
Finding the k-th smallest or largest value (quickselect or a heap instead of a full sort)
Small integer keys, where counting sort beats O(n log n)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio