알고리즘 04 정렬 | 합병정렬 | JS

분할 정복법

• 분할: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
• 정복: 각각의 작은 문제를 순환적으로 해결
• 합병: 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

합병 정렬 | Merge Sort

• 데이터가 저장된 배열을 절반으로 나눔
• 각각의 순환적으로 정렬
• 정렬된 두 개의 배열을 합쳐 전체를 정렬
• 시간복잡도: n*logn

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

function merge(left, right) {
  const result = []
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  while (left.length) result.push(left.shift())
  while (right.length) result.push(right.shift())
  return result
}

📚 참고

YOUTUBE | 2015 봄학기 알고리즘 | 권오흠
합병(머지, 병합) 정렬 by.zerocho

Photo by Michael Dziedzic on Unsplash