합병 정렬(Merge sort)

#들어가기

이번 포스팅에서는 합병 정렬(merge sort)에 대해 알아보겠습니다.

#합병 정렬(merge sort)

합병 정렬(merge sort)은 분할 정복법을 활용한 sort 방법입니다.

분할 정복법은 익히 들어본바와 같이 다음과 같습니다.

• 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
• 정복 : 각각의 작은 문제를 순환적으로 해결
• 합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

그렇다면 이 분할정복법을 어떻게 활용해서 합병 정렬(merge sort)을 할수 있을까요?

• 데이터가 저장된 배열을 절반으로 나눔
• 각각을 순환적으로 정렬
• 정렬된 분할된 리스트를 전체 배열로 합침

문자로 표현하니 조금 난해한 느낌이 있어 다시 그림으로 보겠습니다.

맨 밑에 있는 숫자들이 정렬을 해야하는 숫자들 입니다. 즉, 5-2-4-7-1-3-2-6이 있는 배열을 최대한 작게 나눈 다음 다시 합치는 과정을 그림에서 확인할 수 있습니다.

이제 수도 코드로 간단하게 표현해보겠습니다.

mergeSort(A[], p, r) { // A[p...r]을 정렬
    if(p < r) then {
        q <- (p+r)/2 // 중간 지점을 찾음
        mergeSort(A, p, q); // 앞 부분 정렬
        mergeSort(A, q+1, r); // 뒷 부분 정렬
        merge(A, p, q, r) // 합병
    }
}

void merge(int data[], int p, int q, int r) {
    int i = p, j = q+1, k=p;
    int tmp[data.length()];
    while(i <= q && j <= r) {
        if(data[i] <= data[j])
            tmp[k++] = data[i++];
        else
            tmp[k++] = data[j++];
    }
    while(i <= q)
        tmp[k++] = data[i++];
    while(j <= r)
        tmp[k++] = data[j++];
    for(int i = p; i <= r; i ++)
        data[i] = tmp[i];
}

보시는 것과 같이 합병 정렬(merge sort)은 추가적인 배열(tmp)이 필요합니다.

합병 정렬(merge sort)의 시간 복잡도를 확인해본다면 O(nlogn) 입니다. 이는 합병 정렬(merge sort)가 어떻게 동작하는가를 생각해본다면 쉽게 나올수 있습니다.

즉, 길이가 N인 배열을 계속 반으로 나누는 작업을 진행(O(logn))하면서 합병(O(N))을 수행하기 때문 시간 복잡도는 O(nlogn) 입니다.

#마치며

이로써 합병 정렬(merge sort)의 정리를 마치겠습니다.

#참조

부경대학교 권오흠 교수님 강의 | 2015년 1학기