Merge sort

병합정렬 작성에 필요한 생각의 변화를 작성하고, 구현을 진행한다.

기본규칙

1) unsorted list 를 둔다.
2) 절반씩 나누며 내려간다.
3) 나눈 것을 합치며 sorted sublist 를 만든다.
4) 합칠 것이 없을 때까지 반복한다.

생각의 변화

절반씩 나눠가야 하므로 인자로 sublist 의 정보가 필요

sublist 가 빈 경우를 포함해서 merge 조건문을 작성

합친 결과를 올리려면 받아줄 곳 B가 필요

mid 는 (lo+hi)/2 를 사용

합칠 때 B 내용을 A에 작성
합친 내용은 B 에도 부분적으로 업데이트 필요

pseudo code

merge(&A, lo, mid, hi, &B)
    i = lo
    j = mid+1
    for k=lo  k<=hi  k++
        if i<=mid && (j>hi || B[i] <= B[j])
            A[k] = B[i]
            i++
        else
            A[k] = B[j]
            j++

merge_sort(&A, lo, hi, &B)
    if lo >= hi
        return
    
    mid = (lo+hi)/2
    
    merge_sort(A, lo, mid, B);
    merge_sort(A, mid+1, hi, B);
    
    for  k=lo  k<=hi  k++
        B[k] = A[k]
    
    merge(A, lo, mid, hi, B)

검증

44 69 99 76 71
44 69 99    76 71    M(0 2 4)
44 69     99    M(0 1 2)    76    71    M(3 3 4)
44    69    M(0 0 1)    99    M(0 1 2)

아래에서 위로 merge 시작

44 69 M(0 0 1)
i  j
44 69

44 69 99 M(0 1 2)
i     j
44 69 99

         76 71 M(3 3 4)
         i  j
         71 76
         
44 69 99 71 76 M(0 2 4)
i        j
44 69 71 76 99

         stop

시간복잡도