What this module covers: Merge sort is the first algorithm in this course to fully embody divide-and-conquer: split the problem in half, solve each half recursively (Module P-1), then combine the results. This module covers how that splitting produces O(n log n) instead of Module P-8's O(n²), why merge sort is stable (a property that matters more than it sounds like it should), and its O(n) space cost — the trade-off Module P-10's quicksort makes differently.
The strategy: split the array in half, recursively sort each half, then merge the two already-sorted halves back together in one linear pass — the exact merge logic already built for linked lists in Module P-2, applied here to arrays instead.
function mergeSort(arr: number[]): number[] { if (arr.length <= 1) return arr; // base case (Module P-1)
const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); // recursively sort the left half const right = mergeSort(arr.slice(mid)); // recursively sort the right half
return merge(left, right); // combine two sorted halves into one sorted array }
function merge(left: number[], right: number[]): number[] { const result: number[] = []; let i = 0, j = 0;
while (i < left.length && j < right.length) { if (left[i] <= right[j]) result.push(left[i++]); else result.push(right[j++]); }
// One side will have leftover elements — they're already sorted, append them directly while (i < left.length) result.push(left[i++]); while (j < right.length) result.push(right[j++]);
return result; }
merge is the exact two-pointer shape from Module F-8 and Module P-2's mergeSorted: since both left and right are already sorted, comparing their current fronts and taking the smaller one — repeated until one side runs out — produces a fully sorted result in a single O(n) pass, no re-comparison of anything already placed.
mergeSort splits the array in half, recursively, until reaching single-element arrays (already trivially sorted) — then merges pairs back together on the way back up. The recursion depth is exactly Module F-11's binary-search-style halving: splitting n elements in half repeatedly takes log₂(n) levels to reach single elements.
At each level of this structure, merging back together processes every element exactly once — the total work merging at any single level is O(n), no matter how many pieces that level is split into (four merges of 2 elements each is the same total work as one merge of 8, or two merges of 4). With log(n) levels, each doing O(n) total work, the overall cost is O(n) × O(log n) = O(n log n) — the same complexity class as Module P-10's quicksort (on average), and a full complexity class better than every sort in Module P-8.
At n = 10,000, that's the difference between roughly 10,000 × log₂(10,000) ≈ 133,000 operations (merge sort) and 10,000² = 100,000,000 operations (bubble/selection/insertion sort) — a concrete, enormous gap that only widens as n grows further.
A sort is stable if it preserves the relative order of elements that compare as equal. Merge sort is stable, specifically because of one small detail in merge: left[i] <= right[j] (using <=, not <) always prefers taking from the left side on a tie — and since left came before right in the original array, this guarantees that two equal elements never get reordered relative to each other.
// Sort by age. Stability guarantees Bob still comes before Cal afterward, // since they were already in that relative order before sorting by age.
Why this matters in practice: if you sort a list by one field, then sort the already-sorted result by a second field, a stable sort guarantees that ties on the second field still respect the first field's ordering — this is exactly how "sort by category, then by price within category" works correctly when implemented as two sequential stable sorts, rather than one combined comparator. An unstable sort offers no such guarantee — ties could be reordered arbitrarily, silently breaking the first sort's ordering. This is also part of why React's documentation insists on stable, content-based key props rather than array index — index-based keys interact badly with reordering precisely because index isn't a stable identity across re-renders, a related but distinct stability concern from sorting.
merge allocates a brand-new result array on every single call — this is real, measurable O(n) auxiliary space, on top of the input array, needed at each level of the recursion (though implementations can reuse a single auxiliary buffer across levels rather than allocating fresh each time, the conceptual space cost remains O(n)). This is the direct trade-off against Module P-10's quicksort, which sorts in place with only O(log n) additional space (the recursive call stack) — no second full-size array required. Neither approach is strictly better: merge sort trades memory for a guaranteed O(n log n) worst case (no adversarial input degrades it, unlike quicksort's worst case), and for stability, which quicksort's typical in-place partitioning does not provide without extra care.
External sorting — sorting datasets too large to fit in memory (a common scenario in data pipelines and database engines) — is a direct, large-scale application of merge sort's divide-and-conquer shape: sort manageable chunks that do fit in memory independently, write each sorted chunk to disk, then merge the sorted chunks together in a final pass, the same "combine already-sorted pieces" logic as merge above, just operating on disk-backed data instead of in-memory arrays.
Multi-key sorting ("sort by department, then by salary within department") relies directly on stability: applying two sequential stable sorts (salary first, then department) produces a correctly nested ordering, which would not reliably hold with an unstable sort in between.
Database merge joins: a merge join (one of several join strategies a query planner can choose, alongside hash joins and nested loop joins) works by sorting both input tables on the join key and then merging them with the exact same two-pointer logic as merge above — feasible specifically because both sides are already sorted (often via an existing index), turning the join into a single linear pass rather than comparing every row against every other row.
Array.prototype.sort() at scale (Module P-8's summary already noted this): V8's Timsort-family implementation is, at its core, a heavily optimized merge sort — this module's mergeSort/merge pair is a simplified, but structurally accurate, version of what's actually running under the hood for larger arrays.
Merge sort splits the array in half recursively until reaching single elements, then merges sorted halves back together — the canonical divide-and-conquer shape.
Splitting produces log(n) levels; merging at each level costs O(n) total — combined, O(n log n), a full complexity class better than Module P-8's O(n²) sorts.
Merge sort is stable: using <= (not <) in the merge comparison always prefers the left side on ties, preserving the original relative order of equal elements — essential for correct multi-key sorting.
The trade-off is O(n) auxiliary space for the merge step, versus quicksort's O(log n) space — merge sort buys a guaranteed worst case and stability at the cost of extra memory.
This is the real algorithm behind external sorting, multi-key sorts, database merge joins, and (in optimized form) Array.prototype.sort() on larger arrays.
The next module, Sorting III: Quick Sort and Partitioning, covers the other O(n log n) sort — one that trades merge sort's guaranteed worst case and stability for in-place sorting and typically faster real-world performance.
Knowledge Check
Why does splitting the array in half repeatedly (rather than, say, removing one element at a time) produce O(log n) levels of recursion in merge sort?
Why does merge sort's merge function use left[i] <= right[j] (with <=) rather than left[i] < right[j] (with strict <) when deciding which element to take next?
According to the module, what is the core trade-off between merge sort and quicksort (previewed ahead of Module P-10), specifically regarding space?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
Written by Jatin Jain Saraf · Architect of SupraScan