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

병합정렬은 어떤 경우에도 O(NlogN)의 시간복잡도를 보장합니다.

현재 정렬 순서에 상관없이 분할정복 기법에 의해 일단 반으로 나누고 합치는 과정을 통해 정렬을 수행합니다.

중간 정렬 결과를 담을 임시 변수가 필요하기에 O(N)의 공간복잡도를 가집니다.

---

C++ 소스 코드

#include <iostream>
using namespace std;
int temp[10], nums[10] = {3,6,1,2,9,7,4,5,10,8};
void merge(int s, int m, int e){
    int i=s;
    int j= m+1;
    int k=s;
    while(i<=m &&j<=e){
        if (nums[i]<nums[j]){
            temp[k] = nums[i];
            i++;
        }else {
            temp[k] = nums[j];
            j++;
        }
        k++;
    }
    if (i>m){
        for(int t=j;t<=e;t++){
            temp[k]=nums[t];
            k++;
        }
    }
    if (j>e){
        for(int t=i;t<=e;t++){
            temp[k]=nums[t];
            k++;
        }
    }
    for(int t=s;t<=e;t++){
        nums[t] = temp[t];
    }
}
void merge_sort(int s, int e){
    if (s<e){
        int m = (s+e)/2;
        merge_sort(s,m);
        merge_sort(m+1,e);
        merge(s,m,e);
    }
}
int main(){
    merge_sort(0,9);
    for(int i=0;i<10;i++){
        cout << nums[i] <<' ';
    }
    return 0;
}