병합 정렬

병합 정렬은 분할정복 기법 알고리즘 중 하나이다.

 

분할: 정렬한 n개의 원소의 배열을 n/2개로 분할한다.

정복: 병합 정렬을 이용해 두 부분 배열을 재귀적으로 정렬한다.

결합: 정렬된 두 개의 부분 배열을 병합해 정렬된 배열 하나로 만든다.

 

의 구조로 이루어져있다.

 

의사코드(Pseudo code)

 

MERGE(A,p,q,r)

n1=q-p+1
n2=r-q
배열 L[1...n+1]과 R[1..n+1]을 생성한다.
for i=1 to n1
	L[i] = A[p+i-1]
for j = 1 to n2
	R[j] = A[q+j]
L[n1+1] = ∞
R[n2+1] = ∞
i=1
j=1
for k= p to r
    if L[i] <= R[j]
    	A[k] = L[i]
        i=i+1
    else A[k] = R[j]
    	j=i+1

위는 병합 에 해당하는 부분의 의사코드이다.

 

위 의사코드는 A라는 배열이 있고 이 A라는 배열을 나눈 두 개의 배열이 각각 정렬되어 있을 것이라고 가정한 상태에서 두 배열을 정렬하며 병합하는 알고리즘이다.

 

이를 활용한 병합 정렬의 의사코드는 다음과 같다.

 

MERGE-SORT(A,p,r)

if p < r
	q=⌊(p+r)/2⌋
    MERGE-SORT(A,p,q)
    MERGE-SORT(A,q+1,r)
    MERGE(A,p,q,r)

MERGE 알고리즘을 사용하며 재귀적인 알고리즘이다.

 

위의 MERGE 알고리즘에서는 두 개의 부분 배열이 정렬 되어있는 것을 가정한 상태에서 병합을 시작하는데 재귀적으로 배열을 분열하여 size가 1인 배열을 만든다. 이러한 배열은 정렬되어있으므로 이러한 상태에 도달하였다가 더 이상 분할이 불가능한 순간부터 MERGE 함수를 통하여 병합하여 올라오는 구조로 되어있다.