우크라이나어 하는 개발자

Merge Sort

병합정렬

시간 복잡도: O(nlogn)

공간 복잡도: O(n)

merge 함수는 두 배열을 합쳐 한 배열로 정렬합니다.

mergeSort 함수는 재귀적으로 배열을 나누고 merge 함수로 합칩니다.

/**
 * @param {int[]} leftArr 
 * @param {int[]} rightArr 
 */
const merge = (leftArr, rightArr) => {
  let result = []
  let leftIndex = 0
  let rightIndex = 0
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] < rightArr[rightIndex]) {
      result.push(leftArr[leftIndex])
      leftIndex++
    } else {
      result.push(rightArr[rightIndex])
      rightIndex++
    }
  }
  while (leftIndex < leftArr.length) {
    result.push(leftArr[leftIndex])
    leftIndex++
  }
  while (rightIndex < rightArr.length) {
    result.push(rightArr[rightIndex])
    rightIndex++
  }
  return result
}

/**
 * 
 * @param {int[]} arr 
 */
const mergeSort = (arr) => {
  if (arr.length <= 1) return arr
  let mid = Math.floor(arr.length / 2)
  let left = mergeSort(arr.slice(0, mid))
  let right = mergeSort(arr.slice(mid))

  let result = merge(left, right)
  return result
}