## DSA Tutorial

DSA HOME DSA Intro DSA Simple Algorithm

## Arrays

DSA Arrays DSA Bubble Sort DSA Selection Sort DSA Insertion Sort DSA Quick Sort DSA Counting Sort DSA Radix Sort DSA Merge Sort DSA Linear Search DSA Binary Search

## Stacks & Queues

DSA Stacks DSA Queues

## Hash Tables

DSA Hash Tables DSA Hash Sets DSA Hash Maps

## Trees

DSA Trees DSA Binary Trees DSA Pre-order Traversal DSA In-order Traversal DSA Post-order Traversal DSA Array Implementation DSA Binary Search Trees DSA AVL Trees

## Graphs

DSA Graphs Graphs Implementation DSA Graphs Traversal DSA Cycle Detection

## Shortest Path

DSA Shortest Path DSA Dijkstra's DSA Bellman-Ford

## Minimum Spanning Tree

Minimum Spanning Tree DSA Prim's DSA Kruskal's

## Maximum Flow

DSA Maximum Flow DSA Ford-Fulkerson DSA Edmonds-Karp

## Time Complexity

Introduction Bubble Sort Selection Sort Insertion Sort Quick Sort Counting Sort Radix Sort Merge Sort Linear Search Binary Search

## DSA Reference

DSA Euclidean Algorithm DSA Huffman Coding DSA The Traveling Salesman DSA 0/1 Knapsack DSA Memoization DSA Tabulation DSA Dynamic Programming DSA Greedy Algorithms

## DSA Examples

DSA Examples DSA Exercises DSA Quiz DSA Certificate

# DSA Merge Sort Time Complexity

See this page for a general explanation of what time complexity is.

## Merge Sort Time Complexity

The Merge Sort algorithm breaks the array down into smaller and smaller pieces.

The array becomes sorted when the sub-arrays are merged back together so that the lowest values come first.

The array that needs to be sorted has $$n$$ values, and we can find the time complexity by start looking at the number of operations needed by the algorithm.

The main operations Merge Sort does is to split, and then merge by comparing elements.

To split an array from start until the sub-arrays only consists of one value, Merge Sort does a total of $$n-1$$ splits. Just imaging an array with 16 values. It is split one time into sub-arrays of length 8, split again and again, and the size of the sub-arrays reduces to 4, 2 and finally 1. The number of splits for an array of 16 elements is $$1+2+4+8=15$$.

The image below shows that 15 splits are needed for an array of 16 numbers.

The number of merges is actually also $$n-1$$, the same as the number of splits, because every split needs a merge to build the array back together. And for each merge there is a comparison between values in the sub-arrays so that the merged result is sorted.

During merging of two sub-arrays, the worst case scenario that generates the most comparisons, is if the sub-arrays are equally big. Just consider merging [1,4,6,9] and [2,3,7,8]. In this case the following comparisons are needed:

1. Comparing 1 and 2, result: [1]
2. Comparing 4 and 2, result: [1,2]
3. Comparing 4 and 3, result: [1,2,3]
4. Comparing 4 and 7, result: [1,2,3,4]
5. Comparing 6 and 7, result: [1,2,3,4,6]
6. Comparing 9 and 7, result: [1,2,3,4,6,7]
7. Comparing 9 and 8, result: [1,2,3,4,6,7,8]

At the end of the merge, only the value 9 is left in one array, the other array is empty, so no comparison is needed to put the last value in, and the resulting merged array is [1,2,3,4,6,7,8,9]. We see that we need 7 comparisons to merge 8 values (4 values in each of the initial sub-arrays). In general, in a worst case scenario, $$n-1$$ comparisons are needed to get a merged array of $$n$$ values.

For simplicity, let's say that we need $$n$$ comparisons instead of $$n-1$$ when merging $$n$$ values. This is an ok assumption when $$n$$ is large and we want to calculate an upper bound using Big O notation.

So, at each level merging happens, $$n$$ comparisons are needed, but how many levels are there? Well, for $$n=16$$ we have $$n=16=2^4$$, so 4 levels of merging. For $$n=32=2^5$$ there are 5 levels of merging, and at each level, $$n$$ comparisons are needed. For $$n=1024=2^{10}$$ 10 levels of merging is needed. To find out what power of 2 gives us 1024, we use a base-2 logarithm. The answer is 10. Mathematically it looks like this: $$\log_{2}1024=10$$.

As we can see from the figure above, $$n$$ comparisons are needed on each level, and there are $$\log_{2}n$$ levels, so there are $$n \cdot \log_{2}n$$ comparison operations in total.

Time complexity can be calculated based on the number of split operations and the number of merge operations:

\begin{aligned} O( (n-1) + n \cdot \log_{2}n) {} & = O( n \cdot \log_{2}n ) \end{aligned}

The number of splitting operations $$(n-1)$$ can be removed from the Big O calculation above because $$n \cdot \log_{2}n$$ will dominate for large $$n$$, and because of how we calculate time complexity for algorithms.

The figure below shows how the time increases when running Merge Sort on an array with $$n$$ values.

The difference between best and worst case scenarios for Merge Sort is not as big as for many other sorting algorithms.

## Merge Sort Simulation

Run the simulation for different number of values in an array, and see how the number of operations Merge Sort needs on an array of $$n$$ elements is $$O(n \log n)$$:

{{ this.userX }}

Operations: {{ operations }}

If we hold the number of values $$n$$ fixed, the number of operations needed for the "Random", "Descending" and "Ascending" is almost the same.

Merge Sort performs almost the same every time because the array is split, and merged using comparison, both if the array is already sorted or not.

×

## Contact Sales

If you want to use W3Schools services as an educational institution, team or enterprise, send us an e-mail:
sales@w3schools.com

If you want to report an error, or if you want to make a suggestion, send us an e-mail:
help@w3schools.com

W3Schools is optimized for learning and training. Examples might be simplified to improve reading and learning. Tutorials, references, and examples are constantly reviewed to avoid errors, but we cannot warrant full correctness of all content. While using W3Schools, you agree to have read and accepted our terms of use, cookie and privacy policy.