병합 정렬(Merge Sort)

(참고) 폰 노이만이 고안

QSort, MSort 둘 다 Divide & Conquer 철학에서 나온 것

머지소트는 많은 자료를 한번 정렬하는 것보다 적은 자료를 여러 번 정렬하겠다는 철학에서 나옴

	Q	M
전략	Pivot 기준 절반	무조건 절반
Avg	O(nlogn)	O(nlogn)
Worst	O(n2)	O(nlogn)
공간	자료 공간	자료 공간 * 2

1. 영역 나누기

2. 각 영역 재귀적 진행

3. 두 개의 영역 Merge

-Merge 과정

(S,m) (m+1,e) 두개의 영역을 -> (S,e) 배열로 넣는다.

Idx1, idx2를 이용해 우선순위인 것을 먼저 넣어주고 그 쪽 인덱스를 ++

한쪽이 끝나면 나머지를 전부다 넣어준다.

 

<Code>

void msort(int s, int e)
{
    int l, r, t, m, i; 

    if (s >= e)return;
    l = t = s;
    m = (s + e) / 2;
    r = m + 1; 

    msort(s, m);
    msort(r, e);
    
    while (l <= m && r <= e)tmp[t++] = (a[l] > a[r]) ? a[r++] : a[l++];
    while (l <= m)tmp[t++] = a[l++];
    while (r <= e)tmp[t++] = a[r++];
    
    for (i = s; i <= e; i++)a[i] = tmp[i];
}