[정렬]Merge Sort

합병 정렬(Merge Sort)

배열을 두 구역으로 분리하는 partition과 두 구역을 정렬하며 하나로 합치는 merge로 정렬을 수행하는 stable한 정렬 기법

시간복잡도

O(nlogn)

예시 코드

#include <cstdio>

const int MAX_SIZE = 1000000;
int temp[MAX_SIZE];

void mergeSort(int* arr, int start, int end){
    if(end - start < 2)	   return;
    
    //partition
    int mid = (start + end) / 2;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid, end);
    
    //merge
    int i;
    int l1 = start, l2 = mid;
    for(i = start; i < end; i++)	temp[i] = arr[i];
    i = start;
    while(l1 < mid && l2 < end){
        if(temp[l1] > temp[l2])	   arr[i++] = temp[l2++];
        else	arr[i++] = temp[l1++];
    }
    
    while(l1 < mid)	arr[i++] = temp[l1++];
    while(l2 < end)	arr[i++] = temp[l2++];
}


int main(){
    int arr[10] = {5, 26, 4, 1, 3, 12, -8, 9, 11, 44};
    
    mergeSort(arr, 0, 10);
    
    return 0;
}