분할정복 :합병 정렬 (Merge Sort)

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

// 두 개의 정렬된 배열을 병합하는 함수
void merge(vector<int>& arr, int left, int mid, int right) 
{
    vector<int> temp;  
    int i = left, j = mid + 1;

    // 두 개의 부분 배열을 합친다.
    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) return;

    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

int main() 
{
    vector<int> arr = { 38, 27, 43, 3, 9, 82, 10 };
    mergeSort(arr, 0, arr.size() - 1);

    for (int num : arr) cout << num << " ";
    return 0;
}

 

✅ 합병 정렬은 "분할 정복(Divide and Conquer)"을 활용한 정렬 알고리즘
✅ O(N log N) 시간 복잡도
✅ 큰 문제(배열 정렬)를 작은 문제(부분 배열 정렬)로 나눈 뒤 합치는 방식으로 동작

---

📌 합병 정렬의 핵심 원리

1️⃣ 분할(Divide)

• 배열을 반으로 나눔눔
• 더 이상 나눌 수 없을 때까지(배열의 크기가 1이 될 때까지) 계속 나눔

2️⃣ 정복(Conquer)

• 각 부분을 재귀적으로 정렬
• 정렬된 부분을 병합(Merge)

3️⃣ 합병(Combine)

• 두 개의 정렬된 배열을 합쳐 하나의 정렬된 배열을 만듬

---

📌 코드 분석 (어린이도 이해할 수 있도록)

🔹 코드 핵심 부분

void mergeSort(vector<int>& arr, int left, int right) 
{
    if (left >= right) return; // 배열의 크기가 1이면 종료

    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);  // 왼쪽 절반 정렬
    mergeSort(arr, mid + 1, right);  // 오른쪽 절반 정렬
    merge(arr, left, mid, right);  // 정렬된 두 개를 합치기
}

• 배열을 반으로 나눈다! (mergeSort(arr, left, mid))
• 왼쪽과 오른쪽을 각각 정렬한다! (mergeSort(arr, mid + 1, right))
• 정렬된 두 개의 배열을 합친다! (merge(arr, left, mid, right))

---

🚀 예제로 이해하기 (배열: {38, 27, 43, 3, 9, 82, 10})

📌 Step 1: 처음에는 배열 전체를 반으로 나눕니다.

[38, 27, 43, 3, 9, 82, 10]
       |
       v
[38, 27, 43, 3]  |  [9, 82, 10]  (배열을 두 개로 분할)

---

📌 Step 2: 각각 다시 반으로 나눕니다.

[38, 27, 43, 3] → [38, 27] | [43, 3]
[9, 82, 10] → [9, 82] | [10]

---

📌 Step 3: 더 이상 나눌 수 없을 때까지 계속 나눕니다.

[38, 27] → [38] | [27]
[43, 3] → [43] | [3]
[9, 82] → [9] | [82]

✅ 이제 모든 원소가 한 개짜리 배열이 되었습니다!

---

📌 Step 4: 이제 정렬된 두 개씩 병합을 시작합니다. 1️⃣ [38]과 [27]을 합쳐 정렬 → [27, 38]
2️⃣ [43]과 [3]을 합쳐 정렬 → [3, 43]
3️⃣ [9]과 [82]을 합쳐 정렬 → [9, 82]

---

📌 Step 5: 다시 병합하면서 정렬합니다.

[27, 38]  +  [3, 43]  →  [3, 27, 38, 43]
[9, 82]  +  [10]  →  [9, 10, 82]

---

📌 Step 6: 마지막 병합 (정렬 완료)

[3, 27, 38, 43]  +  [9, 10, 82]  →  [3, 9, 10, 27, 38, 43, 82]

✅ 최종적으로 완전히 정렬된 배열이 됩니다! 🚀

---

🚀 Merge Sort의 시간 복잡도 분석

🔹 분할 과정

• 한 번 실행할 때마다 배열을 1/2로 나눕니다.
• log₂N 번 나누면 배열 크기가 1이 됩니다.
• 따라서, 분할하는 과정의 시간 복잡도는 O(log N) 입니다.

🔹 합병 과정

• 배열을 병합할 때는 모든 원소를 한 번씩 확인합니다.
• 따라서, 합병 과정의 시간 복잡도는 O(N) 입니다.

🔹 전체 시간 복잡도

O(N log N)

✅ 일반적인 O(N²) 정렬보다 훨씬 빠름!

---

📌 정리

단계 설명

1️⃣ 분할 (Divide)	배열을 반으로 계속 나눔
2️⃣ 정복 (Conquer)	배열 크기가 1이 될 때까지 재귀 호출
3️⃣ 합병 (Combine)	정렬된 두 개의 부분 배열을 하나로 합침