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.
The below image will give you a better understanding of the working of 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
      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.
  1. Maximum Sum of Building Speed ( HackerEarth )
  2. Monk’s School ( HackerEarth )
  3. Cheap Thrills ( HackerEarth )
  4. Match Makers ( HackerEarth )
  5. Scoring in Exam ( HackerEarth )

If you find any errors in the article, please comment below.
Written with   💜   by Ashwin

Leave a Reply