Merge Sort

merge_sort.js

//Time Complexity: O(N log N) - mergeSort is called Log N times, each merge iterates over N elements, so N*(Log N)
//Space Complexity: O(N) - the depth of the call stack is Log N, and each recursive call contains a N/2 copy of the array.
//If you sum up each sub array in the call stack this would be N/2 + N/4 + N/8 + 1 which equals N. 
//If new sub arrays were NOT created in each call, then space requirement would be only for the stack frames, which would be Log N.
const mergeSort = (a) => {
  if(a.length === 1) {
    return a;
  }
  let middle = parseInt(a.length / 2);
  let end = a.length;

  //left is exclusive of middle element
  let left = a.slice(0, middle);
  //right is inclusive of middle and end elements
  let right = a.slice(middle, end);

  //split left and right until we have arrays with 1 element
  left = mergeSort(left);
  right = mergeSort(right);

  //combine arrays starting with single elements, then combine those arrays
  return merge(left, right);
}

const merge = (left, right) => {
  //combine left and right to one array to work from
  let a = left.concat(right);
  //create a new empty array the size of array a
  let b = new Array(left.length + right.length);

  let middle = left.length;
  let end = a.length - 1;
  let i = 0;
  let j = middle;

  //loop as many elements as are in array a
  for(let k = 0; k <= end; k++){
    //weave elements taking the lesser of j or i
    //unless we are out of one or the other, 
    //then take the remaining characters of the other
    if(i >= middle || (j <= end && a[j] < a[i])){
      b[k] = a[j];
      j += 1;
    } else {
      b[k] = a[i]; 
      i += 1;
    }
  }
  
  //return the newly built array that is merged left and right
  return b;
}

let a = [3,2,1,4];

let s = mergeSort(a);

//output: [1,2,3,4]
console.log(s)