[정렬] Merge Sort

병합 정렬은 배열을 크기가 1인 배열로 나눈 뒤 각 배열을 병합하며 정렬하는 알고리즘이다.

O(nlogn)의 시간복잡도를 가지기 때문에 매우 안정적이다.

---

#include <iostream>
#include <vector>

using namespace std;

void merge(int arr[], int s, int m, int e){
    vector<int> tmp;
    int s1 = s, s2 = m+1;
    while(s1 <= m && s2 <= e){
        if(arr[s1] > arr[s2]){
            tmp.push_back(arr[s2++]);
        }
        else{
            tmp.push_back(arr[s1++]);
        }
    }
    while(s1 <= m){
        tmp.push_back(arr[s1++]);
    }
    while(s2 <= e){
        tmp.push_back(arr[s2++]);
    }

    for(int i = 0; i < tmp.size(); i++){
        arr[s + i] = tmp[i];
    }
}

void merge_sort(int arr[], int s, int e){
    if(s == e){
        return;
    }
    int m = (s+e)/2;
    merge_sort(arr, s, m);
    merge_sort(arr, m+1, e);
    merge(arr, s, m, e);
}

int main(void){
    int n = 10;
    int arr[10] = {2, 1, 9, 3, 4, 7, 2, 8, 10, 5};

    merge_sort(arr, 0, 9);

    for(int i = 0; i < 10; i++){
        cout << arr[i] << " ";
    }
    cout << "\n";

    return 0;
}