정렬: 병합 정렬

출처: 위키백과

 

병합 정렬이란?

병합 정렬(Merge Sort)은 효율적인 정렬 방법 중 하나로, 분할 정복 알고리즘의 대표적인 예입니다. 배열을 절반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 두 부분을 합치는 방식으로 작동합니다.

 

병합 정렬의 작동 원리

병합 정렬은 전체 배열을 더 이상 나눌 수 없을 때까지 반으로 나누며, 각 부분을 정렬한 다음, 정렬된 부분 배열들을 다시 합치는 과정을 거칩니다. 이 과정에서 정렬된 부분 배열들은 서로 비교되며 최종적으로 전체가 정렬됩니다.

 

병합 정렬의 단계별 과정

1. 배열을 반으로 나눕니다.
2. 각 부분을 재귀적으로 병합 정렬합니다.
3. 정렬된 두 부분 배열을 합쳐 전체를 정렬합니다.

병합 정렬의 복잡도

시간 복잡도: 모든 경우에 O(n log n)입니다.
공간 복잡도: O(n)으로, 배열을 병합할 때 추가적인 공간이 필요합니다.

---

Pseudocode

function mergeSort(arr) {
  if (arr.length > 1) {
    let mid = Math.floor(arr.length / 2);
    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));
    return merge(left, right);
  }
  return arr;
}

function merge(left, right) {
  let result = [], leftIndex = 0, rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex++]);
    } else {
      result.push(right[rightIndex++]);
    }
  }
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

 

실제 예시로 이해하기

예를 들어, [38, 27, 43, 3, 9, 82, 10] 배열을 오름차순으로 정렬해보겠습니다.

1. 배열을 반으로 나눕니다: [38, 27, 43, 3]와 [9, 82, 10]
2. 각 부분을 재귀적으로 병합 정렬합니다.
3. 정렬된 두 부분 [3, 27, 38, 43]와 [9, 10, 82]를 합칩니다.
4. 최종적으로 정렬된 배열 [3, 9, 10, 27, 38, 43, 82]를 얻습니다.

병합 정렬은 그 효율성과 안정성 때문에 대용량 데이터를 처리할 때 매우 유용한 알고리즘입니다. 또한, 분할 정복 방식을 이해하고 익히는 데에도 도움을 줍니다.