Merge Sort Examples in CS Thinking

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.

Read the full concept explanation →

How to Use These Examples

Read the first worked example with the solution open so the structure is clear.
Try the practice problems before revealing each solution.
Use the related concepts and background knowledge badges if you feel stuck.

What to Focus On

Core idea: Merge sort guarantees O(n log n) performance regardless of input 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

Split:

[5,2]

and

[4,1]

See the full worked solution + why-it-works coaching

SetupKey insightWhy it worksCommon pitfallConnection

Unlock answer keys One Family plan — every worked solution, all subjects

Example 2

medium

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(n \log n)

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 = 3

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

n \log_2 n

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(n \log n)

; quicksort averages

O(n \log n)

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(n \log n)

. 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 = 4

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

n \log_2 n

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(n^2)

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]

O(n \log n)

. In which step are inversions counted?

Example 38

hard

Why is the

\Omega(n \log n)

lower bound for comparison-based sorting consistent with merge sort being

O(n \log n)

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?

← Back to Merge Sort Formula Explained Practice Mode

Related Concepts

Sorting Recursion Algorithm Efficiency Bubble Sort Binary Search

Background Knowledge

These ideas may be useful before you work through the harder examples.

sortingrecursionefficiency