[JavaScript] 합병정렬

합병 정렬 (Merge Sort)

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

---

동작 원리

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

---

장점과 단점

• 장점:
  • 안정적인 정렬 (Stable Sort): 동일한 값은 순서가 바뀌지 않습니다.
  • 일관된 시간 복잡도: 최악의 경우에도 O(nlog⁡n)O(n \log n)O(nlogn), 그래서 매우 효율적입니다.
  • 큰 데이터셋에 적합합니다.
• 단점:
  • 추가 메모리 사용: 분할된 배열을 병합할 때 새로운 배열을 생성해야 하므로 O(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(nlogn)
  • 배열을 반으로 나누고, 각 배열을 병합하는 데 O(n)O(n)O(n) 시간이 걸리기 때문에 총 시간 복잡도는 O(nlog⁡n)O(n \log n)O(nlogn)입니다.
• 공간 복잡도: O(n)O(n)O(n)
  • 배열을 분할한 후 병합할 때 새로운 배열을 만들어야 하기 때문에 추가적인 공간이 필요합니다.

---

한 줄 요약

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