How does merge sort work?

It divides the array into halves until each piece has one element, then repeatedly merges adjacent sorted pieces back together until the whole array is sorted.

What is the time complexity of merge sort?

O(n log n) in the best, average, and worst cases. It uses O(n) extra space for the temporary arrays during merging.

Is merge sort stable?

Yes—merge sort is stable, meaning equal elements keep their original relative order, which makes it a good choice when stability matters.

Merge sort vs. quicksort—which is better?

Quicksort is usually faster in practice on arrays because it sorts in place with cache-friendly memory access, but its worst case is O(n²). Merge sort guarantees O(n log n) time and is stable, and it works well for linked lists and data too big to fit in memory, at the cost of O(n) extra space.

Merge Sort Algorithm: Time Complexity & Code

Quick reference

	Complexity
Worst case time	O(n log n)
Best case time	O(n log n)
Average case time	O(n log n)
Space	O(n)

Merge sort is a divide-and-conquer sorting algorithm that splits an array in half, recursively sorts each half, and then merges the two sorted halves back together. It takes O(n log n) time in the best, average, and worst cases, and it's a stable sort, but it needs O(n) extra space.

Strengths:

Fast. Merge sort runs in , which scales well as n grows.
Parallelizable. Merge sort breaks the input into chunks, each of which can be sorted at the same time in parallel.

Weaknesses:

Space. Merge sort takes up extra space, including space for the recursive call stack.

The High-Level Idea

Merge sort is a recursive algorithm that works like this:

split the input in half
sort each half by recursively using this same process
merge the sorted halves back together

Like all recursive algorithms, merge sort needs a base case. Here, the base case is an input array with one item. A one-element array is already sorted.

Splitting the Input

Here's a visual representation of merge sort repeatedly breaking the input array in half:

[8, 3, 2, 7, 9, 1, 4] is broken in half ([8, 3, 2, 7] and [9, 1, 4]). Those halves are broken in half again ([8, 3], [2, 7]; [9], [1, 4]) and again ([8], [3], [2], [7], [9], [1], [4]) until they're just one item each.

At the bottom, we've got a bunch of "sorted" one-item arrays that we want to combine into one large sorted array.

Merging sorted arrays

Combining two one-item arrays is easy—the smaller item goes first and the larger item goes second.

Single-element lists are merged together to make two-element sorted lists. ([8] + [3] -> [3, 8]; [2] + [7] -> [2, 7]; [1] + [4] -> [1, 4]

Now, how do we merge two of these two-item arrays?

That's a bit trickier, and it definitely requires more than one comparison.

Let's come up with a more general algorithm that can merge two sorted arrays of any size.

Take this example:

Two smaller sorted lists ([1, 3, 5] and [2, 6, 8]) will be merged into a sorted list with 6 elements ([_, _, _, _, _, _])

The smallest item has to be the first item in either the first array or the second array. So, we compare the first element in both arrays and place the smaller of the two at the front of the merged array.

The first element in one of the lists ([1, 3, 5]) is 1. The first element in the other list ([2, 6, 8]) is 2.

The first element in one of the lists ([1, 3, 5]) is 1. The first element in the other list ([2, 6, 8]) is 2. 1 is smaller, so it goes at the beginning of our sorted list ([1, _, _, _, _, _])

We can keep repeating this process, skipping over any items that we've already added to the merged array. At each step, we'll just compare the earliest unmerged items from both arrays and add the smaller one.

The merged list is [1, _, _, _, _, _]. Now, we're comparing 3 (from [1, 3, 5]) and 2 (from [2, 6, 8]).

The merged list is [1, _, _, _, _, _]. Now, we're comparing 3 (from [1, 3, 5]) and 2 (from [2, 6, 8]). 2 is smaller than 3, so it goes next in our sorted list, which is now [1, 2, _, _, _, _].

The merged list is [1, 2, _, _, _, _]. Now, we're comparing 3 (from [1, 3, 5]) and 6 (from [2, 6, 8]).

The merged list is [1, 2, _, _, _, _]. Now, we're comparing 3 (from [1, 3, 5]) and 6 (from [2, 6, 8]). 3 is smaller than 6, so it goes next in our sorted list, which is now [1, 2, 3, _, _, _].

The merged list is [1, 2, 3, _, _, _]. Now we're comparing 5 (from [1, 3, 5]) and 6 (from [2, 6, 8]).

The merged list is [1, 2, 3, _, _, _]. Now we're comparing 5 (from [1, 3, 5]) and 6 (from [2, 6, 8]). 5 is smaller than 6, so it goes next in our sorted list, which is now [1, 2, 3, 5, _, _].

Once we exhaust one array, we can just append any remaining items from the other one to the end of the merged array.

All of the items from [1, 3, 5] are in the sorted list. 6 and 8 from [2, 6, 8] still need to be added to the merged list.

6 and 8 are appended to the merged, sorted list, which is now [1, 2, 3, 5, 6, 8]

Using this more general approach, we can easily combine our two-element arrays into four-element arrays, combine those into eight-element arrays, and so on, until all the items are in a single, sorted array.

Small lists ([3, 8]; [2, 7]; [9]; [1, 4]) are merged to form larger sorted lists ([2, 3, 7, 8]; [1, 4, 9]). Those larger lists are merged again into one sorted list with all the items: [1, 2, 3, 4, 7, 8, 9].

Implementation

Here's how we'd code it up:

private static int[] combineSortedArrays(int[] arrayOne, int[] arrayTwo) { int arrayOneIndex = 0; int arrayTwoIndex = 0; int mergedArrayIndex = 0; int[] mergedArray = new int[arrayOne.length + arrayTwo.length]; // both arrays have some items left in them. while (arrayOneIndex < arrayOne.length && arrayTwoIndex < arrayTwo.length) { // choose the smaller of the two items and add it to the // merged array. if (arrayOne[arrayOneIndex] <= arrayTwo[arrayTwoIndex]) { mergedArray[mergedArrayIndex] = arrayOne[arrayOneIndex]; arrayOneIndex += 1; } else { mergedArray[mergedArrayIndex] = arrayTwo[arrayTwoIndex]; arrayTwoIndex += 1; } mergedArrayIndex += 1; } // grab any lingering items in the first array after we've // exhausted the second array while (arrayOneIndex < arrayOne.length) { mergedArray[mergedArrayIndex] = arrayOne[arrayOneIndex]; mergedArrayIndex += 1; arrayOneIndex += 1; } // grab any lingering items in the second array after we've // exhausted the first array while (arrayTwoIndex < arrayTwo.length) { mergedArray[mergedArrayIndex] = arrayTwo[arrayTwoIndex]; mergedArrayIndex += 1; arrayTwoIndex += 1; } return mergedArray; } public static int[] mergeSort(int[] theArray) { // base case: single element array if (theArray.length <= 1) { return theArray; } // split the input in half int middleIndex = theArray.length / 2; int[] left = Arrays.copyOfRange(theArray, 0, middleIndex); int[] right = Arrays.copyOfRange(theArray, middleIndex, theArray.length); // sort each half int[] leftSorted = mergeSort(left); int[] rightSorted = mergeSort(right); // merge the sorted halves return combineSortedArrays(leftSorted, rightSorted); }

Execution Order

We described merge sort as two steps: a splitting step and a merge step.

In reality, these steps are interleaved through recursive calls.

When we split the input into two arrays, we'll actually finish sorting the left half (splitting it all the way down to one-element arrays and merging them back together) before we even touch the right half.

The input list [8, 3, 2, 7, 9, 1, 4] is split in half, with the left half containing [8, 3, 2, 7]. That half gets broken into 1 element lists ([8, 3]; [2, 7] -> [8], [3], [2], [7]), which get merged together ([8] + [3] -> [3, 8]; [2] + [7] -> [2, 7]; [3, 8] + [2, 7] -> [2, 3, 7, 8]). Meanwhile, the right half of the input ([9, 1, 4]) is untouched.

Then, we'll do the same thing with the right half before combining both sorted halves together to get the full sorted array.

The right half of [8, 3, 2, 7, 9, 1, 4] is [9, 1, 4]. That half gets split into single-element lists ([9]; [1, 4] -> [9], [1], [4]), which are merged into sorted lists ([1] + [4] -> [1, 4]; [9] + [1, 4] -> [1, 4, 9]

Understanding the actual execution order is important for thinking through the space cost on the call stack.

Time Complexity

Look at each row in the execution diagram:

The input list ([8, 3, 2, 7, 9, 1, 4]) is broken in half ([8, 3, 2, 7] and [9, 1, 4]), broken in half again ([8, 3]; [2, 7]; [9]; [1, 4]), and again ([8], [3], [2], [7], [9], [1], [4]). The single-element lists are merged together ([8] + [3] -> [3, 8]; [2] + [7] -> [2, 7]; [1] + [4] -> [1, 4]), and merged again ([3, 8] + [2, 7] -> [2, 3, 7, 8]; [9] + [1, 4] -> [1, 4, 9]) and again ([2, 3, 7, 8] + [1, 4, 9] -> [1, 2, 3, 4, 7, 8, 9]) to form the final sorted list.

Each row in the diagram is time.

In the upper half, we do some constant-time work for each item by copying the item from the input array into a smaller array.
In the bottom half, we do some constant-time work for each item by copying the item from a smaller, sorted array into the larger, merged array.

How many rows are there in the diagram? In the top half, we're dividing n in half until we get down to 1. Then, in the bottom half we do the reverse—multiplying by two until we get to n. That's divisions followed by multiplications.. Adding the two together, we've got levels.

So overall, merge sort takes time.

Space Complexity

When combining two sorted arrays into a single bigger one, we need scratch space to hold the merged result.

Since the arrays we'll be combining have items, we'll need space in total.

But, don't we need less than space for some of the merges?

Yes. For instance, when we're merging two arrays with one element each, that requires space.

But, by the time we get to the final merge, we'll have two halves that each have n/2 items, so we'll need space for the combined result.

Do we really need that scratch space? Can't we just be more clever about how we merge the sorted arrays?

Try for yourself! Turns out you can't really do the merge in space without bumping up the time complexity.

If you look carefully, our implementation allocates more memory than is strictly necessary.

In the arguments for each recursive call, we're passing in a copy of half of the input. Over the whole sort, those copies add up to allocated space. (Only of it is in use at any one time, since each level's copies are half the size of the level above.)

We did this to keep the implementation nice and tidy (and not distract from the key intuition behind merge sort).

But with some cleverness, you can get away with allocating a single scratch array up front and reusing it. Try it. :)

Merge Sort vs. Quicksort

Merge sort and quicksort are both divide-and-conquer sorts that average O(n log n) time, but they make different trade-offs:

	Merge sort	Quicksort
Worst-case time	O(n log n)	O(n²)
Average time	O(n log n)	O(n log n)
Extra space	O(n)	O(log n) on average, for the recursion
Stable?	Yes	No (not the usual in-place versions)
Where the work happens	Merging the sorted halves	Partitioning around a pivot

Quicksort is usually faster in practice on arrays, since it sorts in place and moves through memory in a cache-friendly way. Merge sort is the safer pick when you need a guaranteed O(n log n) worst case or a stable sort, or when you're sorting a linked list or data that's too big to fit in memory.

Plenty of standard libraries use both. Java, for example, sorts arrays of primitives with a variant of quicksort and sorts arrays of objects with Timsort, a stable sort built on merge sort.

Interview coming up?

Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.

No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.

No spam. One-click unsubscribe whenever.

You're in! Head over to your email inbox right now to read day one!

Merge Sort Algorithm