mergeSort

mergeSort.js

function sort(originalArray) {
  const arr = [...originalArray]

  if (arr.length <= 1) {
    return arr
  }

  const middleIndex = Math.floor(arr.length / 2)
  const leftArray = arr.slice(0, middleIndex)
  const rightArray = arr.slice(middleIndex, arr.length)
  
  const leftSortedArray = sort(leftArray)
  const rightSortedArray = sort(rightArray)

  return mergeSortedArrays(leftSortedArray, rightSortedArray)
}

function mergeSortedArrays(leftArray, rightArray) {
  const sortedArray = []
  let leftIndex = 0
  let rightIndex = 0

  while(leftIndex < leftArray.length && rightIndex < rightArray.length) {
    let minElement = null

    if (leftArray[leftIndex] < rightArray[rightIndex]) {
      minElement = leftArray[leftIndex]
      leftIndex += 1
    } else {
      minElement = rightArray[rightIndex]
      rightIndex += 1
    }

    sortedArray.push(minElement)
  }

  return sortedArray
    .concat(leftArray.slice(leftIndex))
    .concat(rightArray.slice(rightIndex))
}