Merge and Radix Sort

DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).

Merge Sort and Radix Sort: two very different roads to fast sorting

One divides and conquers. The other never even compares elements directly.

🔀 Merge Sort

IdeaDivide the list in half repeatedly until each piece has 1 element, then merge sorted halves back together, always O(n log n) regardless of input order.

TradeoffNeeds extra memory for the merging step — not "in-place" the way some other sorts are.

Worked example — merge sort tree for [8,3,5,1]: Split: [8,3] [5,1] Split further: [8][3] [5][1] Merge back: [3,8] [1,5] Final merge: [1,3,5,8]

🔢 Radix Sort

IdeaSort numbers digit by digit, starting from the LEAST significant digit, using a stable sort (like counting sort) at each digit position.

Why it's differentNever directly compares two whole numbers against each other — this is what lets it beat the O(n log n) comparison-sort limit, achieving O(nk) for k digits.

💡 Practice a full radix sort pass-by-pass on a list of 4-5 two/three-digit numbers, showing the buckets at each digit position — this exact style of numerical is commonly asked.

Why merge sort is O(n log n) — the two factors

The complexity comes from multiplying two independent quantities, and separating them makes it memorable rather than a fact to recall.

HOW MANY LEVELS? halving until pieces of size 1 → log₂n levels HOW MUCH WORK PER LEVEL? every element is touched exactly once during the merges at that level → n comparisons/moves per level TOTAL = n × log₂n For [8,3,5,1]: 4 elements → log₂4 = 2 levels of splitting, 4 elements handled at each merge level.

Crucially, neither factor depends on the input order. The splitting is positional, and the merging touches everything regardless. That is why merge sort is O(n log n) in the best, average and worst case — unlike quicksort, whose partitioning does depend on the data and degrades to O(n²) on bad pivots.

Why it needs extra memory

Merging two sorted halves into one cannot be done in place without either shifting elements (expensive) or complex bookkeeping. The straightforward implementation writes into a temporary array of size n and copies back.

⚖️ What the O(n) space buys and costs

CostO(n) extra memory, which rules it out where space is tight and makes heap sort preferable there.

Buys: stabilityTaking from the left half when values are equal preserves the original order of equal elements.

Buys: sequential accessMerging reads each run front to back, needing no random access — which is exactly why external sorting is built on merge sort.

💡 That last point ties back to the Types of Sorting topic: merging works on data far larger than memory because it only ever needs the FRONT of each run. Quicksort, jumping around the array, has no such property — the reason merge sort dominates disk-based sorting despite needing more memory in the in-RAM case.

Radix sort and the O(n log n) barrier

Radix sort appears to beat the proven lower bound for sorting. It does not, and the resolution is worth stating.

The O(n log n) bound applies to comparison-based sorts — algorithms whose only operation on the data is comparing two elements. Radix sort never compares anything; it distributes items into buckets by digit. It sidesteps the bound by using extra information — that the keys are numbers with a fixed number of digits — rather than by being a cleverer comparison sort.

💡 So its complexity is O(d·n) for d digits, which beats n log n only when d is small relative to log n. Sorting a million 32-bit integers by 8 hex digits is 8 passes against 20 comparisons per element — genuinely faster. Sorting long strings, where d is large, is not. "Radix sort is O(n), so always use it" is a wrong answer that sounds right.

Syllabus points

Merge sort (divide & conquer)
Radix sort

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.