[병합 정렬] 나누고 정렬하고 다시 합치는 정렬 알고리즘

728x90

병합 정렬(Merge Sort) 

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 전략을 사용하는 대표적인 정렬 알고리즘입니다. 데이터를 더 이상 나눌 수 없을 만큼 작게 쪼갠 뒤, 나눈 조각들을 정렬하면서 다시 하나로 합치는 방식으로 동작합니다.
퀵 정렬과 마찬가지로 평균 시간 복잡도는 O(n log n)이지만, 병합 정렬은 최악의 경우에도 O(n log n)을 보장하며, 안정 정렬이라는 장점도 가집니다. 다만, 추가 메모리 공간이 필요하다는 단점이 있어 메모리 제약이 있는 환경에서는 고려가 필요합니다.
이 글에서는 병합 정렬의 개념, 작동 방식, 다양한 언어로의 구현, 성능 분석을 포함해 병합 정렬이 어떤 상황에서 유용한지 살펴봅니다.

 

---

1.  병합 정렬이란?

Merge Sort

 

병합 정렬은 데이터를 반으로 계속 나누고, 더 이상 나눌 수 없는 단위가 되었을 때 작은 조각부터 서로 비교하며 정렬된 형태로 병합(Merge)해 나가는 방식입니다.

작동 방식

1. 리스트를 반으로 나눈다
   • 배열을 두 개의 절반으로 계속 나눈다.
   • 더 이상 나눌 수 없을 때까지(길이가 1이 될 때까지) 재귀적으로 나눈다.
2. 쪼개진 리스트를 정렬된 상태로 병합할 준비를 한다
   • 각 부분 리스트는 이미 길이 1이므로 정렬된 상태라고 가정한다.
3. 작은 리스트부터 두 개씩 병합하며 정렬
   • 두 리스트를 비교하면서 작은 값부터 새로운 리스트에 차례로 넣는다.
   • 이 과정을 반복하면 점점 더 큰 정렬된 리스트가 만들어진다.
4. 모든 리스트가 병합되면 정렬 완료
   • 최종적으로 하나의 커다란 정렬된 리스트가 만들어진다.

장점

• 시간 복잡도가 항상 O(n log n) → 예측 가능
• 안정 정렬 → 같은 값의 순서 보존
• 분할 정복 방식으로 재귀적 처리에 적합

단점

• 추가 공간 필요 (in-place 정렬 아님)
• 리스트 크기가 작을 경우 다른 정렬보다 느릴 수 있음
• 구현이 비교적 복잡한 편

 

---

2.  예시

초기 배열 : [5, 3, 8, 4, 2, 7, 1, 6]

1. 반으로 나누기 → [5, 3, 8, 4], [2, 7, 1, 6]
2. 계속 나누기 → [5, 3], [8, 4], [2, 7], [1, 6]
3. 더 이상 나눌 수 없을 때, 정렬하며 병합 → [3, 5], [4, 8], [2, 7], [1, 6]
4. 병합 반복 → [3, 4, 5, 8], [1, 2, 6, 7]
5. 최종 병합 → [1, 2, 3, 4, 5, 6, 7, 8]

 

---

3.  언어별 구현 예제

a.  Python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

b.  C++

void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> L(arr.begin() + left, arr.begin() + mid + 1);
    vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);

    int i = 0, j = 0, k = left;
    while (i < L.size() && j < R.size()) {
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    }
    while (i < L.size()) arr[k++] = L[i++];
    while (j < R.size()) arr[k++] = R[j++];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

c.  Java

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge(int[] arr, int left, int mid, int right) {
    int[] leftArr = Arrays.copyOfRange(arr, left, mid + 1);
    int[] rightArr = Arrays.copyOfRange(arr, mid + 1, right + 1);
    int i = 0, j = 0, k = left;

    while (i < leftArr.length && j < rightArr.length) {
        arr[k++] = (leftArr[i] <= rightArr[j]) ? leftArr[i++] : rightArr[j++];
    }
    while (i < leftArr.length) arr[k++] = leftArr[i++];
    while (j < rightArr.length) arr[k++] = rightArr[j++];
}

d.  JavaScript

function mergeSort(arr) {
  // 배열의 길이가 1 이하이면 정렬된 상태로 간주
  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, j = 0;

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

  // 남은 요소들 추가
  return result.concat(left.slice(i)).concat(right.slice(j));
}

 

---

4.  시간 복잡도 분석

케이스	시간 복잡도
최선	O(n log n)
평균	O(n log n)
최악	O(n log n)
공간 복잡도	O(n)
정렬 안정성	안정 정렬

• 항상 균등하게 나누고 병합하므로 성능이 일정합니다.
• 정렬 중 같은 값의 순서를 유지하므로 안정 정렬입니다.
• 병합 단계에서 추가 배열을 사용합니다. → 공간 복잡도 O(n)

 

---

5.  퀵 정렬과 병합 정렬의 차이

분할 정복 공통 흐름

분할 정복 알고리즘은 공통적으로 다음 구조를 따릅니다:

1. 문제를 더 작은 문제로 분할
2. 작은 문제들을 각각 해결
3. 해결한 결과들을 다시 병합

a.  퀵 정렬의 분할 정복

• 분할 : 피벗 기준으로 좌/우 그룹 나누기
• 정복 : 양쪽 그룹에 퀵 정렬 재귀 수행
• 병합 : 병합 생략 (스왑 기반 정렬이므로)

b.  병합 정렬의 분할 정복

• 분할 : 중간 인덱스로 리스트 나누기
• 정복 : 양쪽 각각 병합 정렬 재귀 수행
• 병합 : 정렬된 두 리스트를 병합하여 하나로 만들기

 

---

6.  마무리

• 병합 정렬은 데이터를 잘게 쪼개고, 정렬된 상태로 병합하면서 전체를 정렬하는 알고리즘입니다.
• 항상 일정한 시간 복잡도(O(n log n))를 보장하고, 안정 정렬이라는 장점이 있습니다.
• 다만, 추가 메모리를 사용하는 단점이 있어 사용 환경에 따라 고려가 필요합니다.
• 대규모 정렬, 안정성이 필요한 경우, 또는 외부 정렬(External Sorting) 등에서 매우 유용합니다.

함께 보면 좋은 자료

외부 사이트 :

• Wikipedia - Merge Sort

블로그 글 :

[정렬] 꼭 알아야 할 7가지 정렬 알고리즘 비교 정리

[퀵 정렬] 분할 정복의 정수를 담은 빠른 정렬 알고리즘

 

---

반응형