병합 정렬 알고리즘 성능을 분석합시다.
병합 정렬(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)의 성능을 보여줍니다. 특히 언제나 반 씩 분할한 후에 정복하기 때문에 자료의 배치 상태에 관계없이 일정한 성능을 보여주는 정렬 방식입니다.
그리고 같은 값을 갖고 있을 때 원래 앞에 있는 원소가 정렬 후에도 앞에 있게 정렬하는 안정적인 정렬 알고리즘입니다. 만약 정렬에서 우선적으로 정렬할 키와 차선으로 정렬할 키가 있을 때 차선의 키로 정렬한 후에 우선적인 키로 안정적인 정렬을 수행하면 원하는 결과를 얻을 수 있습니다.
두 개의 키로 정렬하기: 차선의 키로 정렬 → 우선적인 키로 안정적인 정렬