Start with the recap, study the fully worked examples, then use the practice problems to
check your understanding of Merge Sort.
This page combines explanation, solved examples, and follow-up practice so you can move
from recognition to confident problem-solving in CS Thinking.
Concept Recap
A divide-and-conquer sorting algorithm that splits a list in half, recursively sorts each half, then merges the two sorted halves back together in order. The key insight is that merging two already-sorted lists into one sorted list is efficient and straightforward.
Split a messy deck of cards in half, sort each half, then interleave them back in order.
Common stuck point:Merge sort uses extra memory proportional to the input size (unlike in-place sorts).
Sense of Study hint:To understand merge sort, focus on the merge step first: given two sorted lists, produce one sorted list by always picking the smaller front element. Then understand that recursion handles the splitting and sorting—a single-element list is already sorted (base case).
Worked Examples
Example 1
medium
Run merge sort on [5,2,4,1]. Show the result after each phase.Merge sort [5,2,4,1]: split → singletons → merge sorted halves [2,5]+[1,4] → [1,2,4,5]
Answer
[1,2,4,5]
First step
1
Split: [5,2] and [4,1].
See the full worked solution + why-it-works coaching
Setup·Key insight·Why it works·Common pitfall·Connection
Merge [2,5,8,10] and [1,3,6,9]. Give the result.Merge [2,5,8,10] and [1,3,6,9]: two-pointer walk produces sorted output
Example 3
medium
Merge sort [8,3,7,5]. Show splits and final result.Merge sort [8,3,7,5]: split → singletons [8],[3],[7],[5] → merge to [3,5,7,8]
Example 4
hard
Use the recurrence T(n)=2T(n/2)+cn (with T(1)=O(1)) to derive T(n)=O(nlogn) via level-sum argument.
Example 5
hard
A merge step has been written: when one half exhausts, the code does nothing further. What bug manifests, and on what input?
Example 6
hard
Run merge sort on [7,7,3,3]. Verify the order of equal keys is preserved (stability check).
Example 7
challenge
A bottom-up (iterative) merge sort starts by merging adjacent pairs, then quads, then octs. For n=8, how many passes over the array are needed, and what is each pass's cost?
Practice Problems
Try these problems on your own first, then open the solution to compare your method.
Example 1
easy
What is merge sort's time complexity?
Example 2
easy
Merge sort uses which general strategy?
Example 3
easy
Merge two sorted lists [1,4] and [2,3] into one sorted list.Merge [1, 4] and [2, 3]: repeatedly take the smaller front element
Example 4
easy
Does merge sort's running time depend on whether the input is already sorted?
Example 5
easy
Splitting a list of 8 in half repeatedly until size 1: how many split levels?Halving 8 until size 1 takes 3 levels: log₂ 8
Example 6
easy
Merge sort needs roughly how much extra memory?
Example 7
easy
Is the standard merge sort stable (does it preserve order of equal keys)?
Example 8
easy
Merge sort sorts each half before doing what?
Example 9
medium
Merge sort [3,1,2]. Show the result after splitting into [3], [1,2] and merging back.Merge [3] with sorted [1, 2]: fronts 1, 2, 3 in order
Example 10
medium
Merging sorted [1,3,5] and [2,4]: how many element comparisons in the worst case?
Example 11
medium
For n=8, estimate merge sort's total comparisons using nlog2n.
Example 12
medium
Why is merge sort preferred over bubble sort for a 1-million-element list?
Example 13
medium
In the merge step you exhaust the left half first. What must you do with the remaining right-half elements?
Example 14
medium
Merge sort guarantees O(nlogn); quicksort averages O(nlogn) but worst case is what?
Example 15
medium
A merge sort recursion splits until base case size 1. Why is a size-1 list the base case?
Example 16
medium
Merge the sorted lists [2,5,8] and [1,3,9]. Give the merged sorted list.Merge [2, 5, 8] and [1, 3, 9]: take smallest front each step
Example 17
medium
Merge sort [4,2,3,1]. After splitting into [4,2] and [3,1], sorting each, then merging, give the result.Split phase: [4,2,3,1] → [4,2]+[3,1] → singletons; then merge up to [1,2,3,4]
Example 18
challenge
Use the recurrence T(n)=2T(n/2)+n to argue merge sort is O(nlogn). Sketch the level sum.
Example 19
challenge
Merging two sorted halves of sizes n/2 each: give the minimum and maximum number of comparisons, with an input example for each.
Example 20
challenge
Why can merge sort sort data too large to fit in RAM (external sort) while in-place bubble sort cannot help here?
Example 21
easy
Merge two sorted lists [2,6] and [1,4] into a single sorted list.Merge [2, 6] and [1, 4]: take 1, then 2, then 4, then 6
Example 22
easy
Splitting a list of 16 in half repeatedly until size 1: how many split levels?Halving 16 until size 1 takes 4 levels: log₂ 16
Example 23
easy
Merge sort's extra-memory requirement is approximately:
Example 24
easy
Is merge sort stable?
Example 25
easy
Merge [1,5] and [3,7] into one sorted list.Merge [1, 5] and [3, 7]: take 1, 3, 5, then append 7
Example 26
easy
Merge sort uses which paradigm: A) greedy, B) dynamic programming, C) divide and conquer?
Example 27
medium
Merging sorted [1,2,3] and [4,5,6]: how many element comparisons in the worst case?
Example 28
medium
Roughly, how many total comparisons does merge sort use on n=16, using nlog2n?
Example 29
medium
Why does merge sort outperform insertion sort on a one-million-element random list?
Example 30
medium
In the merge step, what do you do when one input half is exhausted?
Example 31
medium
Merge sort vs quicksort: which has O(n2) worst case?
Example 32
medium
Merging [1,2,3,4] and [5,6,7,8]: minimum comparisons needed?
Example 33
medium
How does merge sort behave on an already-sorted list of n?
Example 34
hard
Merging two sorted halves of size n/2 each, give the minimum and maximum number of comparisons.
Example 35
hard
Why is merge sort the default choice for sorting data too large to fit in RAM (external sort)?
Example 36
hard
Compared with in-place quicksort, what is merge sort's most significant downside on RAM-bound systems?
Example 37
hard
Counting inversions: merge sort can compute the number of pairs (i,j) with i<j and A[i]>A[j] in O(nlogn). In which step are inversions counted?
Example 38
hard
Why is the Ω(nlogn) lower bound for comparison-based sorting consistent with merge sort being O(nlogn)?
Example 39
challenge
K-way merge generalizes the merge step to k sorted lists. Using a min-heap, what is the cost to merge k lists with n total elements?
Example 40
challenge
TimSort (used in Python and Java) is a hybrid of merge sort and insertion sort. Why is the hybrid faster on real-world data than pure merge sort?