병합 정렬 (Merge Sort) (C++)

병합 정렬 (Merge Sort)

병합 정렬은 분할 정복(Divide and Conquer) 알고리즘을 사용하는 정렬 기법으로, 배열을 재귀적으로 두 부분으로 나누고, 각각을 정렬한 뒤 병합(Merge)하여 정렬된 배열을 만드는 방식. 안정적이며, 정렬 성능이 O(nlog⁡n)으로 일정한 점에서 효율적.

---

동작 원리

1. 분할 (Divide):
   • 배열을 두 개의 하위 배열로 분할.
   • 하위 배열의 크기가 1이 될 때까지 재귀적으로 반복.
2. 정복 (Conquer):
   • 두 개의 정렬된 하위 배열을 병합하여 하나의 정렬된 배열로 만든다.
3. 병합 (Merge):
   • 병합 과정에서 두 배열을 비교하며 작은 값을 먼저 결과 배열에 추가.

---

특징

• 시간 복잡도:
  • 최선/평균/최악: O(nlog⁡n) (데이터 분할 O(log⁡n), 병합 O(n))
• 공간 복잡도: O(n) (추가 메모리 필요)
• 안정적 정렬: 동일한 값의 순서가 유지.
• 효율성: 데이터 크기와 상관없이 일정한 성능.

---

예제 코드 (C++)

오름차순 병합 정렬

#include <iostream>
#include <vector>
using namespace std;

// 병합 함수: 두 정렬된 배열을 병합하여 하나의 정렬된 배열로 만듦
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp;  // 임시 배열
    int i = left;      // 왼쪽 배열의 시작
    int j = mid + 1;   // 오른쪽 배열의 시작

    // 두 배열을 비교하여 작은 값을 temp에 추가
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp.push_back(arr[i++]);
        } else {
            temp.push_back(arr[j++]);
        }
    }

    // 왼쪽 배열의 남은 요소 추가
    while (i <= mid) {
        temp.push_back(arr[i++]);
    }

    // 오른쪽 배열의 남은 요소 추가
    while (j <= right) {
        temp.push_back(arr[j++]);
    }

    // 정렬된 값을 원래 배열에 복사
    for (int k = left; k <= right; ++k) {
        arr[k] = temp[k - left];
    }
}

// 병합 정렬 함수: 배열을 재귀적으로 분할하고 병합
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);        // 두 부분 병합
    }
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6, 7};
    cout << "정렬 전 배열: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    mergeSort(arr, 0, arr.size() - 1);

    cout << "정렬 후 배열: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    return 0;
}

---

코드 설명

1. merge 함수:
   • 두 개의 정렬된 하위 배열을 병합.
   • 작은 값을 먼저 추가하면서 정렬된 결과를 생성.
2. mergeSort 함수:
   • 배열을 재귀적으로 분할.
   • 각 부분을 병합하여 정렬된 배열로 만든다.
3. 재귀 종료 조건:
   • 배열의 크기가 1 이하일 경우(즉, left >= right) 재귀 호출을 종료.

---

예제 동작 과정

입력 배열: [12, 11, 13, 5, 6, 7]

1. 분할 과정:
   • [12, 11, 13, 5, 6, 7] → [12, 11, 13] & [5, 6, 7]
   • [12, 11, 13] → [12] & [11, 13] → [11] & [13]
   • [5, 6, 7] → [5] & [6, 7] → [6] & [7]
2. 병합 과정:
   • [11] & [13] → [11, 13]
   • [12] & [11, 13] → [11, 12, 13]
   • [6] & [7] → [6, 7]
   • [5] & [6, 7] → [5, 6, 7]
   • [11, 12, 13] & [5, 6, 7] → [5, 6, 7, 11, 12, 13]
3. 최종 정렬된 배열: [5, 6, 7, 11, 12, 13]

---

장점과 단점

장점

• 항상 O(nlog⁡n)의 시간 복잡도를 보장.
• 안정적 정렬: 데이터의 상대적 순서가 유지됨.
• 대규모 데이터에서 일정한 성능.

단점

• 추가 메모리가 필요 (O(n)).
• 작은 데이터 크기에서는 다른 정렬(삽입 정렬 등)보다 느림.

---

활용 사례

• 대규모 데이터 정렬에 적합.
• 안정적 정렬이 필요한 경우(예: 데이터베이스 시스템).