[Algorithm] Merge Sort

세상에는 다양한 정렬 기법이 있다. 이 중 가장 많이 사용되는 것은 Quick Sort와 Merge Sort이다. 오늘은 이 중 Merge Sort에 대해 정리해보겠다. 

 

Merge Sort(병합정렬)

 

기본 개념

Merge Sort는 두 정렬된 배열을 ~N시간에 하나의 배열에 정렬된 상태로 병합할 수 있다는 사실에 기반한 방법이다. 
병합정렬은 정렬한 결과를 다른 배열에 담아야하기 때문에 ~N 만큼의 추가 공간이 필요하다는 단점이 있다. 

 

위와 같이 주어진 배열을 하나짜리 배열로 나눈 뒤 순서대로 병합해 나간다. 

 

시간복잡도

N개 값을 Merge해야하기 때문에 N에 비례한 비교를 진행한다. 그리고 이 과정을 log2(N)회 반복하기 때문에 (반으로 잘라 나가기 때문에) ~Nlog2(N) 의 시간복잡도를 가진다. 

 

코드 (재귀)

def divideNMerge(a, aux, lo, hi):
	if(hi <= lo):
		return a
    mid = (lo + hi) // 2
    divideNMerge(a, aux, lo, mid)
    divideNMerge(a, aux, mid+1, hi)
    merge(a, aux, lo, mid, hi)
    
    
def mergeSort(a):
	aux = [None} * len(a)
    divideNMerge(a, aux, 0, len(a)-1)
    
def merge(a, aux, lo, mid, hi):
	for k in range(lo, hi+1):
    	aux[k] = a[k]
    i, j = lo, mid+1
    for k in range(lo, hi+1):
    	if i > mid: 
        	a[k], j = aux[j], j+1
        elif j > hi:
        	a[k], i = aux[i], i+1
        elif aux[i] <= aux[j]: # stable 하기 위해서는 <= 해야함. < 로 해도 정렬은 됨.
        	a[k], i = aux[i], i+1
        else:
        	a[k], j = aux[j], j+1

 

가장 중앙 값을 mid라고 하고, lo ~ mid, mid+1 ~ hi 로 배열을 분할하였다.

이 코드는 재귀 (함수 안에서 본인의 함수를 부르는 것) 를 사용하였다. 그러다 보니 코드는 깔끔하지만, 공간 사용량이 높다. 왜냐하면 함수를 호출할 때는 함수의 인자, 지역 변수 등을 메모리에 저장하고 삭제하는 과정이 있고, 재귀가 깊어지면 결국 stack 영역의 메모리가 부족해진다.

그럼 재귀를 사용하지 않고 병합정렬을 구할 수 있을까? 가능하다.
우리는 재귀가 끝나는 시점이 배열의 길이가 1인 시점임을 알고 있다. 그렇기 때문에 쪼개는 과정 없이 1에서부터 올라가면 된다.

쪼개지 말고 그냥 올라가자.

 

코드 ( bottom up)

bottom up으로 오면서 약간의 문제가 있다. 1로 시작하고 우리는 2배씩 사이즈를 늘려갈 것인데 정렬할 배열의 크기가 항상 2의 거듭제곱 꼴은 아니기 때문에 2가지 부분에서 문제가 생긴다.

1. 짝을 지어 merge할 배열이 없는 경우
배열의 길이가 7일 때를 생각해보자. 처음에 2개씩 묶다보면 마지막 한 조각이 남는다. 

이런 경우 merge를 하지 않고 넘어가면 된다.

2. merge할 배열은 있으나, 배열의 길이가 완전하지 않은 경우 
위의 예시 상황에서 merge하지 않은 뒤 다음 step을 진행해보자. merge할 배열은 sz=2여야한다. 하지만, 마지막 merge 과정에서는 배열의 크기가 1인 조각이 있다. 이런 경우 2개까지 접근하려면 오류가 날 수 있다. 

이런 상황은 배열의 끝에서만 발생하고, index가 배열의 끝을 넘어가지만 않으면 문제가 발생하지 않는다. 따라서, index가 배열의 길이를 넘어가지 못하도록 하면 된다. 

 

def mergeSort(a):
	aux = [None] * len(a)
    
    sz = 1
    while(sz < len(a)):
    	for lo in range(0, len(a) - sz, sz*2):
        	merge(a, aux, lo, lo+sz-1, min(lo+sz+sz-1, len(a)-1)) # merge 함수는 재귀 코드와 동일
        sz += sz

위 두 가지 사항이 모두 고려된 코드이다. 

1번 상황은 for 문의 range 조건인 len(a)-sz로, 2번 상황은 merge 함수 호출의 마지막 인자에 min(lo+sz+sz-1, len(a)-1) 로 해결하였다. 

 

+) 함수 호출은 항상 좋지 않을까?
함수를 사용하면 가독성이 높아진다. 재귀함수도 사용했을 때 매우 코드가 간결해지는 경우들이 있다. 그래서 프로그램의 성능에 문제가 없을 때는 사용해도 된다. 하지만, 속도 개선이 필요한 경우 함수 호출을 최대한 줄이는 것이 좋다.