합병정렬

void MergeSort(long long int L, long long int R){
    if(L>=R)
        return;
    
    long long int M=(L+R)/2;

    MergeSort(L, M);
    MergeSort(M+1, R);

    for(long long int i=L, l=L, r=M+1; r!=R+1||l!=M+1; i++){
        if((r!=R+1&&l<=M&&arr[l]<arr[r])||r==R+1)
            temp[i]=arr[l++];
        else
            temp[i]=arr[r++];
    }

    for(long long int i=L; i<=R; i++)
        arr[i]=temp[i];
}

 

정렬 구현중 퀵 정렬까지 구현을 했는데 자꾸 최악의 경우 o(n^2)의 시간 복잡도가 나와서 실제로 사용하기 상당히 안 좋았다.

그래서 아에 합병 정렬이라는 새로운 방법을 찾았다.

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

아래 링크를 요약해서 C로 간단히 짠 것이다,.