병합/합병 정렬(Merge Sort)

배열을 절반씩 나누고, 각각을 정렬한 후 병합하는 방식으로 동작

• 재귀로 수행되며 작은 다위부터 정렬이 이루어짐

• 분할 정복 방법을 통해 구현

  → 분할 정복: 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식
  

• 큰 데이터 셋에 적합

  → 추가 메모리를 필요로 하기 때문에 공간 제약이 있는 환경에서는 비효율적일 수 있음
  

진행 과정(오름차순 기준)

1. 배열을 반으로 나누어 두 개의 작은 배열로 분할

   → 더 이상 나눌 수 없을 때까지 반복

2. 나눈 배열들을 각각 정렬된 상태로 유지하며 재귀적으로 정렬 수행

3. 정렬된 두 배열을 병합하면서 하나의 정렬된 배열로 합침

4. 위 과정을 반복하여 최종적으로 완전한 정렬된 배열을 반환

구현 코드(오름차순 기준)

const mergeSort = (arr) => {
  if (arr.length <= 1) return arr; // 배열 길이가 1 이하이면 그대로 반환

  // 1. 배열을 반으로 나누기
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);   // 왼쪽 부분 배열
  const right = arr.slice(mid);     // 오른쪽 부분 배열

  // 2. 나눈 배열을 각각 정렬한 후 병합
  return merge(mergeSort(left), mergeSort(right));
};

// **두 개의 정렬된 배열을 합치는 함수**
const merge = (left, right) => {
  let sortedArr = [];
  let i = 0, j = 0;

  // 1. 두 배열을 비교하면서 작은 값을 새로운 배열에 추가
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      sortedArr.push(left[i]);
      i++;
    } else {
      sortedArr.push(right[j]);
      j++;
    }
  }

  // 2. 남아 있는 요소들을 추가
  return [...sortedArr, ...left.slice(i), ...right.slice(j)];
};

// 테스트
const testArr = [8, 3, 5, 9, 1, 6, 4, 2, 7];
console.log(mergeSort(testArr)); 
// 출력: [1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 복잡도 및 공간 복잡도

• 시간 복잡도
  • 최선: O(n log n)
  • 평균: O(n log n)
  • 최악: O(n log n)
• 공간 복잡도
  • O(n) (추가적인 배열 공간을 사용)