Merge Sorting

// 1. declare a new empty array, and pointers
//  corresponding to indices in arr1 and arr2
//  (set them both to 0)

// 2. if the first element in arr1 is less than the
//  first element in arr2, push the first element in
//  arr1 to the new array, and move the pointer for
//  arr1 one spot to the right. Otherwise, do this for arr2.

// 3. Repeat this process until you've gone through
//  one of the arrays. return the new array,
// concatenated with whatever elements are remaining
//  from the array that you haven't exhausted yet.


// assume arrays are sorted
function merge(arr1, arr2) {
  // 1
  var arr = [];

  // base case
  if(!arr1.length){
    return arr2;
  } else if(!arr2.length){
    return arr1;
  }

  // 2
  if(arr1[0] <= arr2[0]){
    arr.push(arr1.shift());
  } else {
    arr.push(arr2.shift());
  }
  
  // 3
  arr = arr.concat(merge(arr1,arr2));

  return arr;
}


/*
1. If your array has a length less than 2, congratulations!
  It's already sorted.
2. Otherwise, cut your array in half, and consider the
  two sub-arrays separately.
3. Sort each of your smaller subarrays using merge sort.
4. Merge your two subarrays together, and return the
merged array.
*/
function mergeSort(arr) {
  // 1
  if(arr.length < 2){
    return arr;
  } else {
    // 2
    var left, right;
    var idx = Math.floor(arr.length/2);

    // 3
    left = mergeSort(arr.slice(0,idx));
    right = mergeSort(arr.slice(idx));
  }

  // 4
  return merge(left,right);
}