병합 정렬 알고리즘 성능을 분석해 보아요.
병합 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
ah:= n/2
bh:= n – ah;
조건(n이 1보다 작거나 같으면) 종료
병합정렬(base,ah,compare)
병합접열(base+ah,bh,compare)
tbase에 동적 메모리 할당(원소크기*원소개수)
메모리 복사(tbase,base)
ai:=0
bi:=ah
i:=0
반복(ai가 ah보다 작으면서 bi가 n보다 작다)
조건(tbase[ai]가 tbase[bi]보다 작거나 같으면
base[i] := base[ai]
ai:= ai+1
아니면
base[i]:= base[bi]
bi:= bi+1
i:=i+1
반복(ai가 ah보다 작다)
base[i]:= tbase[ai]
i:=i+1
ai:=ai+1
반복(bi가 n보다 작다)
base[i]:= tbase[bi]
i:=i+1
bi:=bi+1
병합 정렬은 배열의 원소가 1개일 때까지 분할하죠.
분할한 두 개의 배열을 하나로 합치기 위해서는 두 배열의 원소 개수만큼 비교해요.
원래 배열을 분할한 배열을 합치기 위해 비교는 n번 수행하겠죠.
결국 분할 횟수 * n 만큼 수행해요.
분할은 원속 개수를 n=>n/2=>n/4… 형태로 분할하므로 2의 h 승이 1이 될 때까지 분할하죠.
수행 속도는 h*n 이예요.
2의 h 승이 n이므로 h는 logn예요.
따라서 수행 속도는 O(nlogn)이라고 말할 수 있어요.