Merge Sort (two different ways)

Merge sort is one efficient algorithm! It’s so efficient, it’s Big O is O(n log N).

In the first way to do merge sort, I will show you through three while loops and two functions total.

const mergeSort = (arr) => {
    let first;
    let second;
    if (arr.length <= 1) {
       return arr
    }
   let middle = Math.floor(arr.length / 2 )
   first = mergeSort(arr.slice(0, middle))
   second = mergeSort(arr.slice(middle))
  return helperFunc(first, second)
}
function helperFunc (first, second) {
     let point = 0
     let point2 = 0;
     let arr = []
     while (point < first.length && point2 < second.length) {
       if (first[point] > second[point2]) {
       arr.push(second[point2])
       point2++
      } else {
       arr.push(first[point])
       point++
      }
}
     while (point < first.length){
        arr.push(first[point]);
        point++;
    }
     while (point2 < second.length){
        arr.push(second[point2]);
        point2++;
    }
      return arr
}

This one uses three while loops. It takes saddles extraneous conditions on both the left and right arrays (aka first and second respectively). The helper function compares every value to each other and pushes it into the array ‘arr’.

Here is the second way to do merge sort using shift().

const mergeSort = (arr) => {
    let first;
    let second;
     if (arr.length <= 1) {
     return arr
    }
    let middle = Math.floor(arr.length / 2 )
    first = mergeSort(arr.slice(0, middle))
    second = mergeSort(arr.slice(middle))
return helperFunc(first, second)
}
function helperFunc (left, right) {
     let point = 0
     let point2 = 0;
     let arr = []
    while (left.length && right.length) {
       if (left[0] <= right[0]) {
           arr.push(left.shift())
       } else {
          arr.push(right.shift())
     }
   }
   return [...arr, ...left, ...right]
}

I prefer the second method, it’s less code. The return statement in the helper function is a concatenation of all that is left over from the left and right arrays.

Happy hacking!

-Crystal