Merge sort is a type of sorting algorithm that recursively breaks down the list of given things into sublists until each sublist can be separately solved. Then these sublists are joined to get our final solution.

It is a comparison-based stable sorting algorithm. This follows the

**divide and conquer**approach since we’re splitting the list into sublists and combining them later.There are two ways to implement this, the top-down implementation uses a recursive mechanism while the bottom-up implementation uses iterative mechanism. Here, we’ll be discussing

**2-way merge sort**.### Pseudo Code

split each element into partitions of size 1

recursively merge adjacent partitions

for i = leftPartIdx to rightPartIdx

if leftPartHeadValue <= rightPartHeadValue

copy leftPartHeadValue

else

copy rightPartHeadValue

copy elements back to the original array

### Implementation in C++

#### Time Complexity

If the running time of merge sort for a list of length n is T(n), then the recurrence relation would be represented as T(n) = 2T(n/2) + n.

Solving the recurrence relation would give us a time complexity of

*O(nlogn)*in worst, best and average case scenarios.#### Space Complexity

Space complexity is asymptotically O(n) regardless of the way the input is stored or the way merge sort is implemented.

**Practice Problems**

For all these problem please write Merge Sort algorithm from Scratch, it will help you to understand the MergeSort Code from depth. After which you can use C++ STL Function which you will be learning later in this Series.

- Maximum Sum of Building Speed ( HackerEarth )
- Monk’s School ( HackerEarth )
- Cheap Thrills ( HackerEarth )
- Match Makers ( HackerEarth )
- Scoring in Exam ( HackerEarth )

If you find any errors in the article, please comment below.