Sorting Algorithms Compared

Almost nothing in a trading system arrives sorted. Trades come off the wire in whatever order the exchange sent them, orders queue at a price level in arrival order, and a signal file lists instruments alphabetically when what you want is the top 50 by expected return. Sorting is the step that makes everything downstream cheap: once data is in order you can binary-search it, merge it, deduplicate it, or take the top-k in one pass.

You will rarely implement a sort in production — every language ships a very good one. But you are expected to know exactly what you are calling, because the four classic algorithms buy you different things and the wrong choice shows up as a latency spike at the worst moment.

The lower bound, and why it matters

Any algorithm that sorts by comparing pairs of elements has to distinguish between $n!$ possible orderings. Each comparison gives one bit of information, so you need at least $\log_2(n!)$ comparisons, which works out to

$$\Omega(n \log n).$$

In words: no comparison sort can beat $n \log n$ in the worst case. Merge sort and heapsort hit that bound; quicksort hits it on average. Sorts that beat it — counting sort, radix sort — do so by not comparing, using the key's structure instead, which only works for small integer-like keys.

The four you need to know

Algorithm	Average	Worst	Extra space	Stable?	Use it when
Merge sort	$n \log n$	$n \log n$	$O(n)$	yes	you need a guarantee and stability, or you are sorting linked/external data
Quicksort	$n \log n$	$n^2$	$O(\log n)$	no	in-memory arrays, speed matters, input is not adversarial
Heapsort	$n \log n$	$n \log n$	$O(1)$	no	worst-case guarantee with no extra memory
Insertion sort	$n^2$	$n^2$	$O(1)$	yes	n is tiny (under ~20) or the data is already nearly sorted

Stable means equal keys keep their original relative order. That sounds academic until you sort orders by price and need same-price orders to stay in arrival sequence — see Stable Sorting and Tie-Breaking.

Worked example: merge sort on eight numbers

Sort [5, 2, 9, 1, 7, 3, 8, 4]. Merge sort splits until pieces are single elements, then merges sorted pieces back:

• Split into [5, 2, 9, 1] and [7, 3, 8, 4], then split again to [5,2] [9,1] [7,3] [8,4].
• Merge each pair: [2,5] [1,9] [3,7] [4,8].
• Merge those: [1,2,5,9] and [3,4,7,8].
• Final merge, comparing heads: 1 vs 3 → 1; 2 vs 3 → 2; 5 vs 3 → 3; 5 vs 4 → 4; 5 vs 7 → 5; 9 vs 7 → 7; 9 vs 8 → 8; then 9. Result [1,2,3,4,5,7,8,9].

Three levels of splitting ($\log_2 8 = 3$) and $n = 8$ work per level gives 24 units of work — the $n\log n$ you were promised, and it never varies with the input.

Worked example: where quicksort goes wrong

Quicksort picks a pivot, partitions the array into "less than pivot" and "greater than pivot", and recurses on both sides. On [5, 2, 9, 1, 7, 3, 8, 4] with pivot 5 you get [2,1,3,4] and [9,7,8] — a near-even split, and the recursion depth is about $\log_2 n$.

Now sort [1,2,3,4,5,6,7,8] while always picking the last element as pivot. Partitioning gives an empty left side and seven elements on the right, then six, then five. That is $n$ levels of $n$ work: $O(n^2)$, on already-sorted data, which is the input you feed it most often in practice.

import random

def quicksort(a, lo, hi):              # average O(n log n), worst O(n^2)
    while lo < hi:
        k = random.randint(lo, hi)     # randomised pivot kills the sorted-input trap
        a[k], a[hi] = a[hi], a[k]
        p = partition(a, lo, hi)
        quicksort(a, lo, p - 1)        # recurse on the smaller side
        lo = p + 1                     # loop on the larger: O(log n) stack

Where it shows up

Interviewers ask you to name the worst case of quicksort, explain why it is still the default, define stability, and pick a sort given constraints ("sort 10 billion rows that do not fit in memory" → external merge sort; "sort ages 0–120" → counting sort). "Sort first" is also the opening move for a huge fraction of array problems — intervals, two-sum variants, and anything that then wants Binary Search Patterns.

In a trading system, matching engines keep price levels ordered and rely on stability for time priority at a level, tick replay merges per-venue files by timestamp (an external merge), and a signal pipeline that only needs the best 50 names should use Quickselect and Top-K Selection in $O(n)$ rather than sorting all 5,000.