On this concept: Formula

Not sure which lesson to do first? Find your level and get a plan →

CS Thinking · Computational Thinking · Grade 9-12

Merge Sort

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.

O(nlog⁡n) time complexity

Quick Answer

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 merge is the clever part: with a finger on the front of each sorted half, you repeatedly copy the smaller front item, so halves with n items in total merge in at most n−1 comparisons. Use merge sort when you need a guaranteed O(nlog⁡n) sort of large data, a stable sort, or a sort of data too big for memory.

Why This Matters

Merge sort turns sorting from O(n2) into O(nlog⁡n), and it guarantees that speed on every input, sorted, reversed or random. For a million items that is about 20 million comparisons instead of about 500 billion. It is stable, so it suits sorting records by several fields, and its merge step is how databases sort files too big for memory. The price is memory: merging needs a second array as large as the input.

Intuitive Explanation

Merging is the key step, so start there. Take two sorted piles, [2, 6, 9] and [3, 4, 10]. Compare the fronts, 2 and 3: take 2. Compare 6 and 3: take 3. Then 6 and 4: take 4. Then 6 and 10: take 6. Then 9 and 10: take 9. The first pile is empty, so copy what is left, 10. Result: [2, 3, 4, 6, 9, 10] after 5 comparisons. Each comparison places one item, so a merge never needs more than n−1 comparisons.

Merge sort gets its sorted piles by splitting. Split [8, 3, 5, 1] into [8, 3] and [5, 1], then into single items; a single item is already sorted, which is the base case. Then merge back up: [8] and [3] give [3, 8]; [5] and [1] give [1, 5]; [3, 8] and [1, 5] give [1, 3, 5, 8]. A list of n items can be halved about log⁡2n times, and each level of merging handles all n items once, so the total is about nlog⁡2n comparisons.

The split always cuts exactly in half, whatever the data looks like, so merge sort has no unlucky inputs. Quicksort, which splits around a chosen pivot, is usually just as fast but falls to O(n2) when the pivots are bad. Merge sort pays for its guarantee with memory, since each merge writes into a new array. Notice also what merging alone cannot do: merge two unsorted lists and the result is still unsorted, because the merge assumes each half is already in order.

Think of it like this. 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.

Core idea. Merge sort guarantees O(n log n) performance regardless of input order.


When to Use

Use merge sort for large lists, when you need a guaranteed O(nlog⁡n) running time, when the sort must be stable (equal items keep their order), or when the data is too big for memory and must be sorted in chunks and merged. For a tiny or nearly sorted list, a simple method such as insertion sort can be faster in practice. If memory is very tight, an in-place method such as heapsort avoids merge sort's extra array.

Tip. Ask: Is a list sorted by splitting it in half, sorting each half, then merging the sorted halves?

How to Recognize It

Look at where the comparing happens: merge sort does almost nothing on the way down and all its comparing during the merges.

  1. Is the list cut into halves again and again until each piece has one item?

    Yes is merge sort's divide phase. If items instead move by swapping neighbors pass after pass, it is Bubble Sort.

  2. Are two already-sorted lists being combined by repeatedly taking the smaller front item?

    Yes is the merge step that gives merge sort its name. If one half is kept and the other thrown away, the method is Binary Search instead.

  3. Is the question specifically about sorting, rather than the general split-solve-combine strategy?

    Yes keeps you at merge sort. If the problem is something else built the same way, such as finding the largest value half by half, it is Divide and Conquer.

  4. Do you need a guaranteed worst case of O(nlog⁡n), or a stable sort?

    Yes favors merge sort. If the list has only a handful of items, a simple method such as Bubble Sort is good enough.

Merge Sort vs Bubble Sort vs Divide and Conquer vs Recursion

Merge sort is a sorting method like bubble sort, an example of divide and conquer, and usually written with recursion. Ask whether the question is about this exact sort, another sort, the general strategy, or a function calling itself.

Merge Sort

Meaning
Merge sort sorts a list by halving it until pieces have one item, then merging sorted pieces back together.
Key test
Split, sort the halves, merge; O(nlog⁡n) even in the worst case.
Formula
T(n)=2T(n/2)+O(n)
Example
[6, 2, 5, 1] splits into [6, 2] and [5, 1], sorts to [2, 6] and [1, 5], merges to [1, 2, 5, 6].

Bubble Sort

Meaning
Bubble sort sorts a list by repeatedly swapping neighboring items that are in the wrong order.
Key test
Only neighbors are compared and swapped; up to n2/2 comparisons.
Formula
O(n2)
Example
[4, 1, 3] becomes [1, 3, 4] after one pass of two swaps.

Divide and Conquer

Meaning
Divide and conquer is a general strategy that splits any problem into smaller copies of itself and combines their answers.
Key test
The question is about the strategy, which also covers problems other than sorting.
Formula
T(n)=aT(n/b)+f(n)
Example
Finding the largest number in a list as the larger of the two halves' largest numbers.

Recursion

Meaning
Recursion is a function calling itself on a smaller input until it reaches a base case.
Key test
A function calls itself; sorting is just one possible use.
Formula
n!=n×(n−1)!
Example
factorial(4) calls factorial(3), which calls factorial(2), down to factorial(1) = 1.

Formula & Notation

O(nlog⁡n) time complexity
Merge sort divides array A[0..n−1] into A[0..m−1] and A[m..n−1] where m=⌊n/2⌋, recursively sorts each half, and merges in O(n) time. Total: T(n)=2T(n/2)+O(n)=O(nlog⁡n).

Worked Examples

Example 1 — Sort eight numbers level by level

Easy

Sort [38, 27, 43, 3, 9, 82, 10, 15] with merge sort. Show each level of merging and count the comparisons.
Show the steps and the answer
  1. Split down to single items: [38] [27] [43] [3] [9] [82] [10] [15].

    A one-item list is already sorted, the base case. 8 items take 3 levels of halving, since 23=8.

  2. Merge pairs: [27, 38], [3, 43], [9, 82], [10, 15], with 1 comparison each, 4 in all.

    Merging two single items takes exactly one comparison.

  3. Merge into fours: [27, 38] with [3, 43] gives [3, 27, 38, 43] in 3 comparisons; [9, 82] with [10, 15] gives [9, 10, 15, 82] in 3 comparisons.

    Each comparison places the smaller front item, and when one side runs out the rest is copied with no comparison.

  4. Final merge: from [3, 27, 38, 43] and [9, 10, 15, 82], take 3, 9, 10, 15, 27, 38, 43 using 7 comparisons, then copy 82.

    The last merge handles all 8 items, so it needs at most 8 − 1 = 7 comparisons.

  5. Total: 4 + 6 + 7 = 17 comparisons.

    Each of the 3 levels costs at most about 8, so the bound is 8×3=24; bubble sort could need 8⋅7/2=28.

Answer: [3, 9, 10, 15, 27, 38, 43, 82], using 17 comparisons.

Takeaway: Merge sort does its real work on the way back up: every level merges all n items, and there are about log⁡2n levels.

Example 2 — Already sorted: no shortcut

Standard

The list [1, 2, 3, 4, 5, 6, 7, 8] is already sorted. Count the comparisons merge sort makes, and compare with a bubble sort that stops after a pass with no swaps.
Show the steps and the answer
  1. First level: merge [1]+[2], [3]+[4], [5]+[6], [7]+[8], 4 comparisons.

    Merge sort splits and merges no matter what order the data is in.

  2. Second level: [1, 2]+[3, 4] compares 1 with 3 and 2 with 3, then copies 3 and 4: 2 comparisons. [5, 6]+[7, 8] also takes 2. Level total: 4.

    On sorted data the left half always runs out first, so each merge needs only as many comparisons as the left half has items.

  3. Last level: [1, 2, 3, 4]+[5, 6, 7, 8] compares 1, 2, 3 and 4 with 5, then copies the right half: 4 comparisons. Merge sort total: 12.

    Every level still runs, and every item is still written into a second array.

  4. Bubble sort with early exit: one pass compares the 7 neighboring pairs, makes no swaps, and stops: 7 comparisons.

    The simple method notices that the data is already in order and quits; merge sort has no way to notice.

Answer: Merge sort makes 12 comparisons and uses an 8-item extra array; bubble sort with early exit makes 7. On sorted input the 'slower' method wins.

Takeaway: Merge sort's O(nlog⁡n) is a guarantee, not a minimum: it never takes advantage of order that is already there.

Example 3 — Find the mistake: a merge that drops items

Application

Lucas writes the merge step as: while both halves still have items, copy the smaller front item to the result. Merging [1, 4, 7] with [2, 3] gives [1, 2, 3]. He says: "The loop ended, so the merge is done." Find the mistake and correct it.
Show the steps and the answer
  1. Trace his loop: 1 vs 2, take 1; 4 vs 2, take 2; 4 vs 3, take 3. The right half is now empty, so the loop stops.

    The loop runs only while both halves have items, and one half ran out first.

  2. Count the items: 5 went in, but [1, 2, 3] has only 3. The 4 and the 7 were dropped.

    A merge must output exactly as many items as it received, which makes counting a quick check.

  3. Add a final step: after the loop, copy whatever remains in either half, in order. Here that is [4, 7].

    The leftovers are already sorted and are all at least as large as everything copied so far, so they go on the end with no comparisons.

  4. Re-run: [1, 2, 3] followed by [4, 7] gives [1, 2, 3, 4, 7], still with 3 comparisons.

    Every item now appears once, in order.

Answer: After the loop, copy the rest of the non-empty half. The merge then gives [1, 2, 3, 4, 7].

Takeaway: A merge is not finished when one half runs out; the other half's leftovers still have to be copied over.

Where You'll See It

  • Merging two sorted spelling-bee sign-up sheets

    Two teachers each hand you an alphabetized list of students. Instead of re-sorting all the names, you walk down both lists with a finger on each, always copying the name that comes first — that finger-walk is exactly the merge step, and it runs in one pass.

  • Combining leaderboards from two game servers

    Each server already keeps its scores in order, so one global leaderboard needs only the merge step: walk down both lists and always take the higher score. Two lists of 500,000 scores merge in fewer than a million comparisons, with no re-sorting at all.

  • Sorting a huge file that does not fit in memory

    When a list is too big for RAM, you sort chunks on disk and merge them back together (external merge sort) — the merge step only needs to look at the front of each chunk, so it streams through giant data using little extra memory at a time.

Common Mistakes

  1. The slip: Merge sort sorts the two halves while it merges them.

    Why it's tempting: The word 'merge' sounds like the place where ordering happens, so students think the comparison-and-merge does the sorting work.

    Instead: Merge sort sorts each half FIRST (recursively); the merge step only interleaves two ALREADY-sorted halves. Merging an unsorted list with another does not produce a sorted result.

  2. The slip: Merge sort is in-place, so it uses no extra memory.

    Why it's tempting: Many sorts (like bubble sort) just swap inside the original array, so students assume all sorts work that way.

    Instead: The standard merge step needs a separate temporary array to hold the merged output, so merge sort uses O(n) extra memory in addition to the input.

  3. The slip: Merge sort can degrade to O(n^2) on a bad input, like quicksort.

    Why it's tempting: Both are divide-and-conquer sorts, so students lump their performance together.

    Instead: Merge sort always splits exactly in half regardless of the data, giving a guaranteed O(n log n) in the worst case. Quicksort's split depends on the pivot, which is why it can hit O(n^2).


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. Merge the sorted lists [3, 8, 12] and [5, 6, 15]. What is the result, and how many comparisons does the merge make?

    Hint: Always compare the two front elements and take the smaller one.

  2. Use merge sort on [38, 27, 43, 3]. Show the splits and each merge.

    Hint: Split until each list has one item, then merge pairs back up.

  3. Merge sort halves a list of 16 items again and again. How many levels of splitting until every piece has 1 item? About how many element moves happen in total?

    Hint: Count how many times 16 can be halved. Each level moves every item once.

  4. Merge sort sorts 1,000,000 numbers, each stored in 4 bytes. About how much extra memory does merging need?

    Hint: Merging copies items into a temporary list about as long as the input.

  5. Your sort must never be slower than O(nlog⁡n), even on the worst possible input, and extra memory is available. Merge sort or quicksort?

    Hint: Compare each algorithm's worst case, not its average.

  6. A student's merge stops as soon as one list runs out. Merging [1, 4] and [2, 3, 9], it gives [1, 2, 3, 4]. What went wrong?

    Hint: Look at what is left in the second list when the first is empty.

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

Why is merge sort O(nlog⁡n)?

Picture the splitting as levels. Halving a list of nn items until pieces have one item takes log⁡2n\log_2 n levels: 8 items split into 4s, 2s and 1s, which is 3 levels. At each level the merges together handle every item once, about nn steps. So the total is about nn steps on each of log⁡2n\log_2 n levels: roughly 24 steps for 8 items and about 20 million for a million.

If merge sort is so reliable, why is quicksort often used instead?

Quicksort sorts inside the original array, so it needs almost no extra memory, and in practice its inner loop is very quick. Its weakness is a bad pivot choice, which can make it O(n2)O(n^2), though choosing pivots at random makes that extremely unlikely. Merge sort's guaranteed speed and stability make it the choice when those matter, as in Python's built-in sort, which is based on merge sort.

Does merge sort do less work on a list that is already sorted?

The basic version does not notice: it still splits everything and merges every piece. The merges get a little cheaper, because one half runs out quickly, so a sorted list of 8 needs 12 comparisons instead of up to 17. Smarter versions such as Timsort first look for runs that are already in order and merge those, so a sorted list takes only about nn steps.

Learning Path

Merge Sort

You are here

You need Sorting (key and direction), Recursion (base case and smaller calls) and Algorithm Efficiency (comparing n2 with nlog⁡n) first. Merge Sort adds the merge step and the split, sort, merge pattern that sorts any list in O(nlog⁡n). Next, Bubble Sort is the useful contrast, the simple O(n2) method, and Binary Search shows what a sorted list makes possible.

See Also