[JavaScript] 합병정렬

KIMJAVAN 2025. 1. 11. 18:07

728x90

합병 정렬 (Merge Sort)

합병 정렬은 **분할 정복 알고리즘 (Divide and Conquer)**의 일종으로, 큰 문제를 작은 문제로 나눈 후 그 결과를 합쳐서 해결하는 방식으로 동작합니다. 이 알고리즘은 매우 효율적이며, 시간 복잡도가 **최악의 경우에도 O(nlog⁡n)O(n \log n)**입니다.

동작 원리

분할 (Divide):
- 배열을 반으로 나눕니다. 이 과정을 배열의 크기가 1이 될 때까지 재귀적으로 반복합니다.
정복 (Conquer):
- 배열이 하나의 요소만 남을 때까지 분할한 후, 각 배열을 정렬합니다.
병합 (Merge):
- 두 개의 정렬된 배열을 하나의 정렬된 배열로 합칩니다.
- 이때, 두 배열을 비교하면서 더 작은 값을 차례대로 새로운 배열에 넣습니다.

장점과 단점

장점:
- 안정적인 정렬 (Stable Sort): 동일한 값은 순서가 바뀌지 않습니다.
- 일관된 시간 복잡도: 최악의 경우에도 O(nlog⁡n)O(n \log n), 그래서 매우 효율적입니다.
- 큰 데이터셋에 적합합니다.
단점:
- 추가 메모리 사용: 분할된 배열을 병합할 때 새로운 배열을 생성해야 하므로 O(n)O(n)만큼 추가적인 메모리가 필요합니다.
- 배열을 일일이 비교하고 병합하는 과정에서 다른 정렬 알고리즘보다 상대적으로 느릴 수 있습니다.

합병 정렬 구현 (JavaScript)

const mergeSort = (array) => {
  // 배열의 크기가 1 이하라면 이미 정렬된 배열
  if (array.length <= 1) return array;

  // 배열을 두 부분으로 나누기
  const middle = Math.floor(array.length / 2);
  const left = array.slice(0, middle);
  const right = array.slice(middle);

  // 왼쪽과 오른쪽 배열을 각각 정렬 후 병합
  return merge(mergeSort(left), mergeSort(right));
};

// 병합 함수: 두 정렬된 배열을 하나로 합친다.
const merge = (left, right) => {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // 두 배열을 비교하면서 작은 값을 result에 삽입
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // 남은 값들을 모두 결과 배열에 추가
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
};

const an = [5, 1, 4, 2, 8];
console.log(mergeSort(an)); // [1, 2, 4, 5, 8]

합병 정렬 동작 예시

배열: [5, 1, 4, 2, 8] (오름차순 정렬)

1단계 (분할)

[5, 1, 4, 2, 8] → [5, 1, 4]와 [2, 8]로 나눔
[5, 1, 4] → [5]와 [1, 4]로 나눔
[1, 4] → [1]과 [4]로 나눔
[2, 8] → [2]와 [8]로 나눔

2단계 (정복 및 병합)

[1]과 [4]를 병합 → [1, 4]
[5]와 [1, 4]를 병합 → [1, 4, 5]
[2]와 [8]을 병합 → [2, 8]
[1, 4, 5]와 [2, 8]을 병합 → [1, 2, 4, 5, 8]

결과: [1, 2, 4, 5, 8]

시간 복잡도

최선, 최악, 평균 모두: O(nlog⁡n)O(n \log n)
- 배열을 반으로 나누고, 각 배열을 병합하는 데 O(n)O(n) 시간이 걸리기 때문에 총 시간 복잡도는 O(nlog⁡n)O(n \log n)입니다.
공간 복잡도: O(n)O(n)
- 배열을 분할한 후 병합할 때 새로운 배열을 만들어야 하기 때문에 추가적인 공간이 필요합니다.

한 줄 요약

합병 정렬은 배열을 반으로 나누어 정렬하고, 나중에 병합하여 완성하는 효율적인 정렬 알고리즘입니다. 대규모 데이터에 적합하며, 항상 O(nlog⁡n)O(n \log n)의 성능을 보장합니다. 😊