# Merge Sort

Merge sort is a

*divide and conquer algorithm*that sorts an array.With

*merge sort*, the input array is split into multiple subproblems.Each subproblem is then

*merged*into the result array.For example, let's say you're given the following array of numbers.

arr = [3, 1, 5, 2, 9, 8]

The image below shows the steps that the array is sorted.

## Try it

Before you look at the solution, try to code it yourself.

## Solution

### Time Complexity

It takes

*logarithmic time*to divide the problem into subprobems.*Merging*the sorted sub arrays into the output takes

*linear*time.

Therefore, the overall time complexity of the merge sort is

`O(n*log n)`

.## 5 Essential Sorting & Searching Coding Interview Problems

Master Sorting & Searching by trying the coding challenges below.

- 1.Merge intervalsMedium
- 2.Kth largest in arrayMedium
- 3.Intersection of ArraysMedium
- 4.Search sorted matrixHard
- 5.Search row & col sorted matrixHard