[정렬] 병합 정렬

1. 설명

• 분할 정복(Divide and Conquer) 알고리즘
• 배열을 반씩 나누고 정렬한 후 병합하는 방식
• 시간복잡도는 항상 O(n log n)
• 대량 데이터에 적합하지만 추가적인 메모리 공간 사용

2. 코드

#include <iostream>
#include <vector>

using namespace std;

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

    int i = 0, j = 0, k = left;
    while (i < leftArr.size() && j < rightArr.size()) {
        if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];
        else arr[k++] = rightArr[j++];
    }

    while (i < leftArr.size()) arr[k++] = leftArr[i++];
    while (j < rightArr.size()) arr[k++] = rightArr[j++];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    
    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 = {64, 25, 12, 22, 11};
    mergeSort(arr, 0, arr.size() - 1);

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