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.
Showing a random 20 of 50 problems.
Example 1
easy
Merge sort uses which general strategy?
Example 2
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?
Example 3
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 4
hard
Run merge sort on [7,7,3,3]. Verify the order of equal keys is preserved (stability check).
Example 5
easy
Merge sort's extra-memory requirement is approximately:
Example 6
medium
For n=8, estimate merge sort's total comparisons using nlog2n.
Example 7
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 8
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 9
medium
Merge sort guarantees O(nlogn); quicksort averages O(nlogn) but worst case is what?
Example 10
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 11
medium
How does merge sort behave on an already-sorted list of n?
Example 12
easy
Merge sort uses which paradigm: A) greedy, B) dynamic programming, C) divide and conquer?
Example 13
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 14
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 = 3
Example 15
hard
Merging two sorted halves of size n/2 each, give the minimum and maximum number of comparisons.
Example 16
easy
Merge sort needs roughly how much extra memory?
Example 17
easy
What is merge sort's time complexity?
Example 18
medium
Merging sorted [1,2,3] and [4,5,6]: how many element comparisons in the worst case?
Example 19
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?
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?