Merge Sort

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.

Visualization



The below image will give you a better understanding of the working of merge sort.


The video given below will provide an in-depth explanation.

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.

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


Written with by Ashwin

Comments