The Merge Sort algorithm is a very important question that you may have heard in your school or college asked in many interviews including FAANG companies.


Merge sort is one of the most popular sorting algorithms and it uses the concept of divide and conquers to sort a list of elements. Meaning, It will divide the bigger array into smaller arrays and then solve each of the small arrays in order to solve the bigger array that we started out with. 


Merge Sort Working:


Let's take an array [10, -1, 2, 5, 0, 6, 4, -5]


This is obviously an unsorted array. We must sort this array using merge sort. Merge sort requires dividing the problem into smaller problems. So, let's look at a diagram of how this will look like:



Notice that at each level we divide the array into two halves until we get a bunch of single-element arrays. This is the divide portion of the divide and conquer method. Then, we start merging and sorting the smaller arrays in a series of steps which is the conquer portion of divide and conquer.


Let's start with the algorithm


var mergesort = function(arr) {

  if (arr.length < 2) {

    return arr

  }

  const mid = Math.floor(arr.length / 2)

  const leftArr = arr.slice(0, mid)

  const rightArr = arr.slice(mid)

  return merge(mergesort(leftArr), mergesort(rightArr))

}


function merge(leftArr, rightArr) {

  const sortedArr = []

  while (leftArr.length && rightArr.length) {

    if (leftArr[0] <= rightArr[0]) {

      sortedArr.push(leftArr.shift())

    } else {

      sortedArr.push(rightArr.shift())

    }

  }

  const resultArr = [...sortedArr, ...leftArr, ...rightArr]

  return resultArr

}


const arr = [8, 20, -2, 4, -6]

console.log(mergesort(arr)) // [-6, -2, 4, 8, 20]



 Merge Sort Complexity


Time Complexity: 


Best Case Complexity: O(n*log n)


Worst Case Complexity: O(n*log n)


Average Case Complexity: O(n*log n)


Space Complexity:


The space complexity of the merge sort is O(n).


I hope you understood the algorithm. If you have any doubts, please let us know in the comments.