9.4.1 병합 정렬 알고리즘 성능 분석

병합 정렬 알고리즘 성능을 분석합시다.

병합 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

조건(n<=1) 종료

    h:=n/2

병합 정렬(base, h, compare)

병합 정렬(base+h, n- h, compare)

    ai:=0    bi:=h    ci:=0

    tbase에 크기 n인 버퍼 할당

반복(ai<h 이면서 bi<n)

조건(compare(base[ai],base[bi])>0)

            tbase[ci] := base[bi]    bi++

아니면

            tbase[ci]:= base[ai]    ai++

        ci++

반복(ai<h)

        tbase[ci]:=base[ai]    ai++, ci++

반복(bi<n)

        tbase[ci]:=base[bi]    ci++, bi++

    base에 tbase 내용 복사

    tbase 메모리 해제

병합 정렬에서 분할 과정은 n개일 때 1, n/2일 때 두 번(분할한 두 개가 각각 한 번 분할),…해서 총 n-1번 분할합니다.

분할 횟수 = 1+2+4+8+…+n/2 = n-1

정복 과정에서는 분할 횟수가 h이고 분할한 h개를 h/2개로 병합하기 위해 비교 회수는 최악일 때 n보다 작습니다. 분할 횟수는 logN이므로 정복에 들어가는 전체 비용은 NlogN보다 작습니다.

정복 과정에서의 비교 횟수<=NlogN

따라서 병합 정렬의 전체 비용은 최악일 때 O(NlogN)이라고 말할 수 있습니다. 앞에서 살펴본 힙 정렬과 마찬가지로 병합 정렬은 O(NlogN)의 성능을 보여줍니다. 특히 언제나 반 씩 분할한 후에 정복하기 때문에 자료의 배치 상태에 관계없이 일정한 성능을 보여주는 정렬 방식입니다.

그리고 같은 값을 갖고 있을 때 원래 앞에 있는 원소가 정렬 후에도 앞에 있게 정렬하는 안정적인 정렬 알고리즘입니다. 만약 정렬에서 우선적으로 정렬할 키와 차선으로 정렬할 키가 있을 때 차선의 키로 정렬한 후에 우선적인 키로 안정적인 정렬을 수행하면 원하는 결과를 얻을 수 있습니다.

두 개의 키로 정렬하기: 차선의 키로 정렬 → 우선적인 키로 안정적인 정렬