병합 정렬 (Merge Sort) 설명과 JavaScript 예제

병합 정렬은 대표적인 분할 정복(Divide and Conquer) 알고리즘으로, 배열을 절반으로 나누고 각각 정렬한 후 다시 병합하여 정렬을 완성하는 방식입니다. 시간 복잡도가 항상 일정(O(n log n))하기 때문에 안정적이며, 정렬 성능이 중요한 경우 많이 사용됩니다.

---

1. 동작 원리

1. 배열을 반으로 나눔 (재귀적으로 반복)
2. 더 이상 나눌 수 없을 때까지 분할
3. 두 개의 정렬된 배열을 병합하면서 하나의 정렬된 배열로 만듬

이러한 구조는 재귀 호출과 정렬된 병합이 핵심입니다.

---

2. JavaScript 예제 - 오름차순 정렬

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.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));
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

• 배열을 계속 반으로 나눈 뒤, merge() 함수로 정렬 병합
• 병합 과정은 항상 두 배열이 정렬되어 있다는 가정 하에 수행됨

---

3. 성능 분석

구분	시간 복잡도
최선의 경우	O(n log n)
평균	O(n log n)
최악의 경우	O(n log n)

• 공간 복잡도: O(n) → 임시 배열 사용 필요
• 안정 정렬: 동일한 값의 순서가 유지됨

---

4. 병합 정렬의 특징

• 항상 일정한 시간 복잡도 → 예측 가능한 성능
• 배열의 크기가 클수록 버블, 선택, 삽입 정렬보다 월등한 성능
• 공간이 허용된다면 매우 효율적인 알고리즘

---

마무리

병합 정렬은 많은 정렬 알고리즘 중에서도 안정적이고 신뢰할 수 있는 성능을 제공하는 방식입니다. 특히 대용량 데이터를 다룰 때 유용하며, 내부적으로 다른 고급 정렬에서도 병합 정렬 방식이 활용되기도 합니다.

단점은 추가 메모리 공간이 필요하다는 점이므로, 메모리 제한이 있는 환경에서는 주의가 필요합니다.