cf.completefrontend
SORTING · CORE

Merge sort

Split the list in half, sort each half, then merge the two sorted halves into one sorted list.

Time O(n log n)Space O(n)8 practice problemsStep-through picture

The idea

Merge sort uses one powerful fact: two lists that are already sorted can be combined into one sorted list quickly. You look at the front of each list, take the smaller item, and repeat. This is called merging, and it takes one pass.

So merge sort splits the list into two halves, sorts each half (by splitting them again, and again, until each piece has one item), and then merges the pieces back together. A list of one item is already sorted, so the splitting stops there.

Merge sort always takes O(n log n) time, even on the worst input, and it is stable: equal items keep their order. The price is extra memory for the merged lists.

An everyday example

Two sorted stacks of exam papers

Two teachers each sort half of the class's exams by score. To combine them, you put both stacks face up and compare the top papers. You take whichever has the lower score and put it on a new pile. Repeat until one stack is empty, then put the rest of the other stack on top. To get two sorted stacks in the first place, each teacher splits their own pile and hands it to helpers, all the way down to single papers.

How the example maps to the code
In the exampleIn the code
Splitting the pile among helpersmergeSort(items.slice(0, middle)) and mergeSort(items.slice(middle))
A single paper: already sortedif (items.length <= 1) return items
Comparing the two top papersleft[i] <= right[j]
Putting the lower one on the new pileresult.push(...)
Adding what is left of the other stackThe two while loops at the end of merge

From the slow way to merge sort

  1. Simple sorts like insertion sort cost O(n²) because each comparison fixes at most one out-of-order pair, and a random list has about n² / 4 of them. To go faster, each step has to settle many pairs at once. So look for a job that is easy when part of the order is already known.
  2. Here is one: two lists that are each sorted can be combined into one sorted list in a single pass. The smallest item overall must be at the front of one of the two lists, so compare the two fronts, take the smaller, and repeat. Combining n items this way, called merging, takes at most n - 1 comparisons.
  3. Merging needs sorted lists to start with. Where do they come from? Split the list in half and sort each half the same way. Each half splits again, and again, until the pieces have one item. A list of one item is already sorted, so the splitting stops there and the merging can begin.
  4. How much work is that? Halving n items down to single items takes about log₂ n levels. On each level, the merges together touch every item once. So the total is about n × log₂ n steps, whatever the input looks like. Split in half, sort both halves with the same function, and merge: that recursion is merge sort.

How it works

  1. If the list has 0 or 1 items, it is sorted: return it.
  2. Find the middle index, middle = Math.floor(items.length / 2).
  3. Sort the left half and the right half with the same function (recursion).
  4. Merge: keep an index i into left and j into right. Push the smaller of left[i] and right[j] into result and move that index forward.
  5. When one side runs out, push the rest of the other side.
  6. Return result, which holds every item in sorted order.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function mergeSort(items) {
  2. if (items.length <= 1) return items;
  3. const middle = Math.floor(items.length / 2);
  4. const left = mergeSort(items.slice(0, middle));
  5. const right = mergeSort(items.slice(middle));
  6. return merge(left, right);
  7. }
  9. function merge(left, right) {
  10. const result = [];
  11. let i = 0;
  12. let j = 0;
  13. while (i < left.length && j < right.length) {
  14. if (left[i] <= right[j]) {
  15. result.push(left[i++]);
  16. } else {
  17. result.push(right[j++]);
  18. }
  19. }
  20. while (i < left.length) result.push(left[i++]);
  21. while (j < right.length) result.push(right[j++]);
  22. return result;
  23. }

How fast it is

TimeO(n log n)
Extra memoryO(n)

There are about log₂ n levels of splitting, and each level merges all n items once. The merged arrays need O(n) extra memory.

  • Best caseO(n log n)

    An already sorted list like [1, 2, 3, 4, 5, 6, 7, 8]. Each merge empties left after about half the comparisons, but the code still splits, copies, and merges every level.

  • Average caseO(n log n)

    A random list: log₂ n levels, each merging all n items once.

  • Worst caseO(n log n)

    Lists where the fronts keep alternating, so each merge makes the full n - 1 comparisons. It is still log₂ n levels: about 20 million steps for a million items.

Common mistakes

  • Leaving out the base case, or writing items.length === 0. A one-item list then splits into an empty list and itself forever.
  • Using < instead of <= in the merge. The sort still sorts, but equal items can change order, so it is no longer stable.
  • Forgetting the leftover loops after the main merge loop. The tail of one half is silently dropped.
  • Calling shift() on arrays to take the front item. Each shift moves every other item, making the merge O(n²). Use indexes.

When to use it

Look for these clues in a problem:

  • You need a guaranteed O(n log n) sort, or a stable sort.
  • The data is a linked list, where merging is easy and random access is slow.
  • The question counts pairs across two halves, such as out-of-order pairs, which can be counted during the merge.
  • The input is two or more lists that are already sorted and must be combined.

Check yourself

Answer each one in your head first, then open it.

Why is the base case items.length <= 1 and not items.length === 0?

A one-item list would split into [] and itself, and calling mergeSort on itself never makes progress. Stopping at one item, which is always sorted, ends the recursion.

What is the most comparisons one merge of a 3-item and a 4-item list can make?

Six, which is 3 + 4 - 1. Each comparison places one item, and the last item is placed without a comparison once the other side is empty.

Why does merge sort take O(n log n) even on a sorted list?

The code always splits down to single items and copies every item at every level. Nothing checks whether a half is already in order.

What makes merge sort stable, and what single change breaks it?

Taking from left when items are equal, with left[i] <= right[j]. Changing it to < takes the right copy first, so equal items can swap order.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 8 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The proof has two parts: merging is correct, and the recursion is correct. For merging, the rule at the top of the main loop is: result holds the smallest i + j items of left and right, in sorted order. It starts empty, so it is true.

Each step keeps that rule. Both inputs are sorted, so the smallest item not yet taken is left[i] or right[j], whichever is smaller. Pushing it adds the next smallest item to the end of result. When one side runs out, everything left on the other side is at least as big as what was taken, and already sorted, so pushing it all keeps result sorted.

For the recursion, use induction on the length. A list of 0 or 1 items is returned as it is, and it is sorted. A longer list splits into two strictly shorter halves, because middle is at least 1 and less than the length. If mergeSort sorts every shorter list, both halves come back sorted, and merging them gives the whole list sorted. The halves keep getting shorter, so the recursion always reaches the base case.

Stability comes from the tie rule. Every item in left was before every item in right in the original list. Taking from left when left[i] <= right[j] keeps that order for equal items at every level.

Going deeper

3 more ideas

Why merging works

Both halves are sorted, so the smallest item not yet merged is always at the front of one of them: left[i] or right[j]. Taking the smaller of the two is always right. Using <= takes from the left when they are equal, so an item from the left half stays ahead of its equal twin from the right half. That is what makes merge sort stable.

Why it is O(n log n)

Halving n items down to single items takes about log₂ n levels. At each level, the merges together touch every item once, which is O(n) work per level. So the total is O(n log n) in every case: a million items need about 20 levels of a million steps each.

Bottom-up merge sort

You can skip the recursion. Treat each item as a sorted run of length 1, merge neighboring runs into runs of length 2, then 4, then 8, until one run covers the list. This uses the same merge step and is how many library sorts, including TimSort, combine runs.

Work it by hand

Every step in a table, with why

Sort 6 numbers with two 6s. The recursion is shown merge by merge, then the final merge step by step.

items = [5, 8, 1, 6, 2, 6]

StepStepleftrightresultWhat happensWhy
1mergeSort of all 6---middle = 3The list splits into [5, 8, 1] and [6, 2, 6]. The left half is sorted first.
2mergeSort([5, 8, 1])---middle = 1[5] is a base case and comes back as it is. [8, 1] splits into [8] and [1].
3merge[8][1][1, 8]8 <= 1 is false: take 1One comparison. Then right is empty, so the leftover loop adds 8.
4merge[5][1, 8][1, 5, 8]Take 1, then 55 <= 1 is false, then 5 <= 8 is true. left is empty, so 8 is added. The left half is sorted.
5mergeSort([6, 2, 6])---middle = 1[6] is a base case, and [2, 6] splits into [2] and [6].
6merge[2][6][2, 6]2 <= 6: take 2Then the leftover 6 is added.
7merge[6][2, 6][2, 6, 6]Tie: take the left 6 first6 <= 2 is false, so take 2. Then 6 <= 6 is true, so the 6 from left goes first. That is what keeps equal items in their original order.
8Final, i = 0, j = 0[1, 5, 8][2, 6, 6][1]1 <= 2: take 1Both halves are sorted. Now merge them.
9i = 1, j = 0[1, 5, 8][2, 6, 6][1, 2]5 <= 2 is false: take 2The right front is smaller, so j moves.
10i = 1, j = 1[1, 5, 8][2, 6, 6][1, 2, 5]5 <= 6: take 5The left front is smaller again.
11i = 2, j = 1[1, 5, 8][2, 6, 6][1, 2, 5, 6]8 <= 6 is false: take 68 waits while the right side has smaller items.
12i = 2, j = 2[1, 5, 8][2, 6, 6][1, 2, 5, 6, 6]Take the second 6Now j = 3, so right is used up and the main loop ends.
13leftovers[1, 5, 8][2, 6, 6][1, 2, 5, 6, 6, 8]Push the rest of leftwhile (i < left.length) adds 8. The other leftover loop does nothing.

It returns [1, 2, 5, 6, 6, 8] after 11 comparisons in 5 merges. The recursion ends at the 6 one-item base cases, and each merge ends when one side is used up.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Merge sortO(n log n)O(n)You need a guaranteed O(n log n) and a stable result, or you are sorting a linked list or data too large for memory.
Quick sortO(n log n)O(log n)You sort numbers in place, don't need stability, and want the fastest average time. Use random pivots to avoid the O(n²) case.
Heap sortO(n log n)O(1)You need guaranteed O(n log n) with no extra memory, and stability doesn't matter.
Insertion sortO(n²)O(1)The list has fewer than a few dozen items or is nearly sorted. Merge sort implementations often switch to it for tiny pieces.

Extra memory: O(n): the merged arrays and the slices together hold a few copies of the input at most. The recursion is only log₂ n calls deep, about 20 for a million items.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Merge sort and the other approaches, on a scale where each line up is 10 times more steps.
  • Merge sort, Quick sort, Heap sort O(n log n)
  • Insertion sort O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Merge sort339,96620 million
Quick sort339,96620 million
Heap sort339,96620 million
Insertion sort1001 million1 trillion

Inputs that need care

5 tricky inputs
An empty list [] or one item [3]
items.length <= 1 returns the same array at once. Note that for longer lists the result is a new array, while these two cases return the input itself.
Duplicates: [4, 1, 4, 1]
The <= in merge takes the left copy first, so equal items keep their original order. The result is [1, 1, 4, 4].
Already sorted or reversed lists
Both take O(n log n). Merge sort does not get faster on sorted data unless you add a check, such as skipping the merge when left's last item is <= right's first.
Objects, like tasks with a due date
left[i] <= right[j] compares objects as strings or numbers, which is wrong. Pass a compare function and use compare(left[i], right[j]) <= 0 instead.
A very large list, like 5 million numbers
The recursion is only about 23 calls deep, so the stack is safe. The memory is the problem: slice and result allocate many short-lived arrays. A bottom-up version with one reusable buffer avoids that.

Variations and follow-ups

Twists interviewers add

Bottom-up merge sort

Skip the recursion: merge neighboring runs of length 1, then 2, then 4, until one run covers the list. With one extra buffer that is swapped back and forth with the input each round, it allocates only once.

Natural merge sort

Instead of splitting at fixed midpoints, find the runs that are already sorted in the input and merge those. A sorted list is one run and needs no merging, so it takes O(n). TimSort is a refined version of this idea.

K-way merge

Merge k sorted lists at once by keeping the front item of each in a min-heap. Each step pops the smallest and pushes the next item from the same list: O(n log k) in total. It is used to merge sorted files and paginated results.

Merge sort on linked lists

A linked list can be split with a slow and fast pointer and merged by relinking nodes, with no extra arrays. That makes merge sort the usual choice for sorting linked lists, where quick sort's random access is slow.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it when the problem says "stable", "linked list", "merge k sorted", or asks to count something about pairs across two halves, like inversions. Those are all merge steps in disguise.
  • Explain it in two sentences: "merging two sorted lists is one linear pass, and a one-item list is sorted. So split in half, sort each half the same way, and merge." Then give the levels-times-work argument for O(n log n).
  • Test by hand with an odd length (to check middle and the base case), a list with duplicates (to check <= and stability), and a list where one half is used up early (to check the leftover loops).
  • Expect "can you do it with less memory?". Answer: bottom-up merge sort with one reused buffer still needs O(n) extra space. True in-place merging exists but is complex and slower, so heap sort is the usual answer when memory must be O(1).

Where frontend code uses it

The same idea in real UI code
  • V8's Array.prototype.sort uses TimSort, a merge sort hybrid. Since ES2019 the language requires sort to be stable, which merge-based sorts give naturally.
  • Combining two already sorted lists, such as messages from a local cache and from the server (both sorted by time), is one merge step: O(n) instead of sorting again.
  • Sorting data too large to hold at once, such as a big CSV export processed in chunks, sorts each chunk and then merges them.

Related algorithms