Drill 22: Make it smaller — Sorting algorithms

function insertionSort(values) {
  const items = [...values]
  for (let i = 1; i < items.length; i++) {
    const current = items[i]
    let j = i - 1
    while (j >= 0 && items[j] > current) {
      items[j + 1] = items[j]
      j--
    }
    items[j + 1] = current
  }
  return items
}

function mergeSort(values) {
  if (values.length <= 1) return values
  const mid = Math.floor(values.length / 2)
  const left = mergeSort(values.slice(0, mid))
  const right = mergeSort(values.slice(mid))
  return merge(left, right)
}

function merge(left, right) {
  const result = []
  let i = 0
  let j = 0
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++])
    else result.push(right[j++])
  }
  return result.concat(left.slice(i)).concat(right.slice(j))
}

const numbers = [5, 2, 9, 1, 5, 6]
console.log(insertionSort(numbers))
console.log(mergeSort(numbers))
console.log(numbers.sort((a, b) => a - b))