합병 정렬(Merge Sort)

합병 정렬(Merge Sort)는 기본 아이디어를 3단계로 나눌 수 있다.

# 합병 정렬 Process

정렬해야 할 A라는 리스트 [6,2,8,1,3,9,4,5,10,7] 이 있다고 하자

1. A를 이등분하여 L = [6,2,8,1,3], R = [9,4,5,10,7]로 만든다. 

2. L과 R을 각각 정렬한다.

3. L 과 R을 합병하여 정렬된 리스트 S = [1,2,3,4,5,6,7,8,9,10]을 만든다.

이를 ADL로 표현하면 다음과 같다.

mergeSort(a[],l,r)
	if (r>l) then {
    	m <- (r+1)/2;
        mergeSort(a[],l,m);
        mergeSort(a[],m+1,r);
        merge(a[],l,m,r);
    }
end mergeSort()

전체적인 MergeSort 알고리즘은 이와 같다. mergesort는 merge가 핵심이다. 두개의 정렬된 리스트 L과 R을 하나의 정렬된 리스트 S로 합병할 때, 공백 리스트 S에 작은 원소를 삭제하여 첨가하는 방식을 반복 수행하여 정렬한다.

이를 표현하는 ADL은 다음과 같다.

merge(a[],l,m,r):
	i <- l; j <- m+1; k <- l;
    while ( i<= m and j<=r) do {
    	if (a[i] < a[j]) then {
        	b[k] <- a[i];
            k <- k+1; i <- i+1;
        }
        else {
        	b[k] <- a[j];
            k <- k+1; j <- j+1;
        }
    }
    if (i > m) then
    	for (p <- j; p <- r; p <- p+1) do {
        	b[k] <- a[p];
            k <- k+1;
        }
    else
    	for (p <- i; p <= m; p <- p+1;) do {
        	b[k] <- a[p];
            k <- k+1;
	for (p <- l; p<= r; p <- p+1) do {
    	a[p] <- b[p];
end merge()

이를 그림과 예시를 통해서 보이면 다음과 같다.

다음은 [6,2,8,1,3,9,4,5,10,7] 에 대한 합병 정렬 과정이다.

합병정렬 과정

합병 정렬 알고리즘 입력배열에 민감하지 않아 안정적이지만 N에 비례하는 추가 기억 장소가 필요하여 제자리 정렬은 아니다. 그리고 합병정렬은 최악의 경우에도 \( O(NlogN) \) 이다.

 

python code'는 다음과 같다.

def merge(a,l,m,r):
    b = a.copy()
    for i in range(m+1,l,-1):
        b[i-1] = a[i-1]
    i -= 1
    for j in range(m,r):
        b[r+m-j] = a[j+1]
    j += 1
    for k in range(l,r+1):
        if b[i] < b[j]:
            a[k] = b[i]
            i += 1
        else:
            a[k] = b[j]
            j -= 1
    return a

def mergeSort(a,l,r):
    if r>l:
        m = (r+l)//2
        mergeSort(a,l,m)
        mergeSort(a,m+1,r)
        merge(a,l,m,r)
    return a