mergeSort.js

describe('The `mergeTwoSortedArrays` function', () => {
  it('merges two sorted arrays', async () => {
    expect(mergeTwoSortedArrays([1, 3, 5, 7], [2, 4, 6, 8, 10])).toEqual([
      1,
      2,
      3,
      4,
      5,
      6,
      7,
      8,
      10
    ])
  })
})

function mergeTwoSortedArrays(arr1, arr2) {
  let mergedArr = []
  let i = 0
  let j = 0
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      mergedArr.push(arr1[i])
      i++
    } else {
      mergedArr.push(arr2[j])
      j++
    }
  }
  while (i < arr1.length) {
    mergedArr.push(arr1[i])
    i++
  }
  while (j < arr2.length) {
    mergedArr.push(arr2[j])
    j++
  }
  return mergedArr
}

describe('The `mergeSort` function', () => {
  it('sorts an array', async () => {
    expect(mergeSort([5, 3, 2, 1, 4])).toEqual([1, 2, 3, 4, 5])
  })
})

function mergeSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    arr[i] = [arr[i]]
  }
  let sortedArr
  do {
    sortedArr = []
    for (let i = 0; i < arr.length; i = i + 2) {
      sortedArr.push(mergeTwoSortedArrays(arr[i], arr[i + 1] || []))
    }
    arr = sortedArr
  } while (sortedArr.length > 1)
  return sortedArr[0]
}