9.4 병합 정렬(Merge Sort)

이제 병합 정렬 알고리즘을 살펴보기로 해요.

병합 정렬은 배열을 분할한 후에 분할한 배열끼리 정렬하는 것을 반복하여 전체를 정렬하는 알고리즘입니다. 이처럼 커다란 문제를 작은 문제로 분할하고 분할한 작은 영역의 문제를 해결하면서 커다란 문제를 해결하는 알고리즘을 분할 정복(Divide And Conquer) 알고리즘이라고 말합니다.

먼저 분할하는 과정이 필요합니다. 분할하다가 원소의 개수가 1보다 작거나 같으면 분할은 끝납니다.

조건(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와 같거나 bi가 n과 같으면 한 쪽 배열의 나머지 원소를 임시 버퍼에 옮깁니다.

반복(ai<h)

tbase[ci]:=base[ai]

ai++, ci++

반복(bi<n)

tbase[ci]:=base[bi]

ci++, bi++

마지막으로 임시 버퍼의 내용으로 원래 배열에 복사한 후에 임시 버퍼의 메모리를 해제합니다.

base에 tbase 내용 복사

tbase 메모리 해제

다음은 병합 정렬 알고리즘의 의사 코드입니다.

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