MergeSort

mergeSort.js

function mergeSort (array= []) {
  if (array.length == 1) return array

  const middle = Math.floor(array.length / 2) 
  const leftHalf = array.slice(0, middle) 
  const rightHalf = array.slice(middle)


  return mergeHalves(
    mergeSort(leftHalf),
    mergeSort(rightHalf)
  )
}

function mergeHalves(left =[],right=[]) {
  let sortedArray = []
  let indexLeft = 0
  let indexRight = 0


  while (indexLeft < left.length && indexRight < right.length) {
    if (left[indexLeft] < right[indexRight]) {
      sortedArray.push(left[indexLeft])
      indexLeft++
    } else {
      sortedArray.push(right[indexRight])
      indexRight++
    }
  }

  return [...sortedArray, ...left.slice(indexLeft),...right.slice(indexRight)]
}

Order: O(nlogn)

In merge sort, we break the given array midway, for example, if the original array had 6 elements, then merge sort will break it down into two subarrays with 3 elements each.

But breaking the original array into 2 smaller subarrays is not helping us in sorting the array.

So we will break these subarrays into even smaller subarrays until we have multiple subarrays with a single element in them. Now, the idea here is that an array with a single element is already sorted, so once we break the original array into subarrays which has only a single element, we have successfully broken down our problem into base problems.