[Practice] Merge sort

[lpatmo]

Implement merge sort.

[lpatmo]

function merge(arr1,arr2) {
  let results = [];
  let i = 0, j = 0;
  while(i < arr1.length && j < arr2.length) {
    if (arr2[j] > arr1[i]) {
      results.push(arr1[i])
      i++;
    } else {
      results.push(arr2[j]);
      j++;
    }
  }
  while (i < arr1.length) {
    results.push(arr1[i])
    i++;
  }
  while (j < arr2.length) {
    results.push(arr2[j])
    j++;
  }
  return results;
}
function mergesort(input) {
  //arrays of 0 or 1 elements are always sorted
  //decompose an array into smaller arrays (e.g. split in half, split again, get to single arrays. Then merge them together.)
  if (input.length <= 1) {
    return input;
  }
  let mid = Math.floor(input.length/2)
  return merge(mergesort(input.slice(0,mid)), mergesort(input.slice(mid)))
}