Merge Sort and Divide-and-Conquer

Merge sort is the reliable O(n log n) sort: it guarantees that bound in every case, is stable, and is the model divide-and-conquer algorithm. Interviewers use it to test recursion, the merge step, and its role in counting inversions and sorting linked lists.

The core idea

Divide the array in half, recursively sort each half, then merge the two sorted halves in linear time with two pointers. The recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n) by the Master Theorem. It needs O(n) auxiliary space for the merge (O(1) for linked lists via pointer splicing) and is stable. The merge step also counts "split inversions", giving an O(n log n) inversion-count algorithm.

Aspect	Value
Time (all cases)	O(n log n)
Space (array)	O(n)
Space (linked list)	O(1)/O(log n)
Stable	Yes
Recurrence	2T(n/2) + O(n)

Exam Tricks & Tips

• 🎯 Merge sort guarantees O(n log n) in the worst case — unlike quicksort's O(n²).
• 🎯 It's stable, so use it when equal elements must keep their order.
• 🎯 Best sort for linked lists (no random access needed; O(1) extra space bottom-up).
• 🎯 The merge step counts inversions in O(n log n) — a classic follow-up.
• 🎯 External merge sort handles data too big for memory (sort chunks, merge streams).
• ❌ Common mistake: an unstable or O(n²) merge — always merge with two pointers taking the left element on ties.

Expected pattern

Sort an array/list, count inversions, "count of smaller numbers after self", or external sort reasoning. Interviewers expect the divide-merge structure, the O(n log n) guarantee, and stability.

Quick recap

Merge sort divides, recursively sorts, and merges in O(n) — guaranteed O(n log n), stable, O(n) space (O(1) for lists). It's the model divide-and-conquer and the basis for O(n log n) inversion counting and external sorting.

Cover the answer, recall, then check. 11 cards on merge sort and divide-and-conquer.

Q1. Merge sort's time complexity in all cases?
A1. O(n log n) — best, average, and worst.

Q2. Its recurrence relation?
A2. T(n) = 2T(n/2) + O(n), which solves to O(n log n).

Q3. Space complexity for arrays?
A3. O(n) auxiliary space for the merge step.

Q4. Is merge sort stable?
A4. Yes — take the left element on ties during merge.

Q5. Why is merge sort ideal for linked lists?
A5. It needs no random access, and bottom-up merging uses O(1) extra space.

Q6. How does the merge step count inversions?
A6. When taking a right-half element before left-half remainder, add the count of remaining left elements. O(n log n).

Q7. The three divide-and-conquer phases?
A7. Divide (split), conquer (recursively sort halves), combine (merge).

Q8. Cost of the merge of two sorted halves of total size n?
A8. O(n) with two pointers.

Q9. When is merge sort preferred over quicksort?
A9. When a guaranteed O(n log n), stability, or linked-list/external sorting is required.

Q10. What is external merge sort for?
A10. Sorting data larger than memory: sort chunks that fit, then merge the sorted runs.

Q11. Merge sort's main drawback vs quicksort?
A11. O(n) extra space and generally worse cache locality/constants for in-memory arrays.

Merge sort is the reliable O(n log n) sort — guaranteed, stable, and the template for divide-and-conquer thinking. It also powers counting inversions and external sorting of data too big for memory.

Core idea: divide the array in half, conquer by recursively sorting each half, then combine by merging two sorted halves into one. Merging two sorted arrays of total size n is a linear scan, and the recursion has log n levels, giving O(n log n).

How it works

Beginner — the recursion

def mergeSort(a):
    if len(a) <= 1: return a
    mid = len(a)//2
    left  = mergeSort(a[:mid])
    right = mergeSort(a[mid:])
    return merge(left, right)     # two-pointer merge of sorted halves

The merge walks both halves with two pointers, always taking the smaller front element → O(n) per level.

Intermediate — the complexity, precisely

The recurrence is T(n) = 2·T(n/2) + O(n). By the Master Theorem this is O(n log n) in all cases (best, average, worst) — merge sort never degrades. The price is O(n) auxiliary space for the merge buffer (arrays), though on linked lists it can be O(1) auxiliary and O(log n) stack.

Advanced — stability, inversions, and external sort

• Stable: taking from the left half on ties preserves order — important when sorting records by a secondary key.
• Counting inversions: during the merge, when a right-half element is taken before left-half elements remain, they form inversions — count them in the same O(n log n) pass.
• External merge sort: sort chunks that fit in RAM, then k-way merge them from disk — the standard way to sort data larger than memory.

Worked example

Merge sort [38, 27, 43, 3]. Split → [38,27] and [43,3]. Sort halves → [27,38] and [3,43]. Merge with two pointers: 3<27 → 3; 27<43 → 27; 38<43 → 38; then 43. Result [3,27,38,43]. Two levels of splitting, each merge O(n), total O(n log n).

When to use it

• Guaranteed O(n log n) sorting where worst-case matters (unlike quicksort's O(n²)).
• Stable sorting (sort by multiple keys), sorting linked lists (no random access needed).
• Counting inversions, "how far from sorted", and external sorting of huge datasets.

Tricks & gotchas

• Merge sort needs O(n) extra space (arrays) — a downside versus in-place quicksort/heapsort.
• It is stable; quicksort typically is not — choose merge sort when stability is required.
• The merge step is the reusable primitive (merge k lists, count inversions).
• Mnemonic: "Split to singletons, merge upward — n log n, always."

Key formulas

• Recurrence T(n) = 2T(n/2) + Θ(n) ⇒ Θ(n log n) (Master theorem case 2).
• Always Θ(n log n) worst case; stable; O(n) auxiliary space.
• Merging two lists of sizes p, q needs ≤ p+q−1 comparisons.
• Recursion depth ⌈log₂ n⌉; work per level Θ(n).
• Counts inversions in Θ(n log n).

Usage: recognise the 2T(n/2)+n pattern as n log n instantly.

Worked Example

Problem: Sort [38, 27, 43, 3] using merge sort, showing the divide and merge steps.

Solution: Merge sort divides the array in half recursively, then merges sorted halves.

Divide:

[38, 27, 43, 3]
-> [38, 27]      [43, 3]
-> [38] [27]     [43] [3]

Merge (combine two sorted lists by repeatedly taking the smaller front element):

• [38] + [27] → [27, 38]
• [43] + [3] → [3, 43]
• [27, 38] + [3, 43] → compare fronts: 3, 27, 38, 43 → [3, 27, 38, 43]

The recurrence T(n) = 2T(n/2) + O(n) gives O(n log n) time. Merge sort is stable and needs O(n) auxiliary space.

Answer: [3, 27, 38, 43].