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 each one, 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?
Common stuck point:Merge sort uses extra memory proportional to the input size (unlike in-place sorts).
Ask yourself:Is a list sorted by splitting it in half, sorting each half, then merging the sorted halves?
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.
Merge sort is like sorting a tall stack of exam papers with a group of friends: keep halving the stack and passing halves on until each person holds a single paper, which is already sorted. Then pairs of people combine their piles by repeatedly taking the lower-scoring of the two top papers, until one sorted stack is left. A program does the passing on with recursion.