[알고리즘] 합병 정렬 (Merge Sort) 이란?

합병 정렬 (Merge Sort) 이란?

분할 정복 방법을 통해 구현하는 정렬 방식이다. 주어진 배열을 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기 순으로 재배열 하면서 원래 크기의 배열로 합친다.

* 분할 정복이란?

큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식

빠른 정렬로 분류되며, 퀵소트와 함께 많이 언급되는 정렬 방식이다.

퀵 소트와는 반대로 안정 정렬이다.

 

과정

1. 하나의 배열을 두 개로 쪼갠다.

[6, 5, 3, 1, 8, 7, 2, 4]

2. 원소의 개수가 1개 이하로 더이상 쪼갤 수 없을 때까지 쪼개진 배열에 대해 1번을 반복한다.

[6, 5, 3, 1] [8, 7, 2, 4]

[6, 5] [3, 1] [8, 7] [2, 4]

[6] [5] [3] [1] [8] [7] [2] [4]

3. 더 이상 쪼개지지 않는 경우, 두 개씩 합치기를 시작한다. 각 배열 내에서 가장 작은 값을 서로 비교하여 더 작은 값을 먼저 선택하면 자연스럽게 크기 순으로 선택이 된다.

[5, 6] [1, 3] [7, 8] [2, 4]

[1, 3, 5, 6] [2, 4, 7, 8]

4. 최종적으로 마지막 2개의 배열도 크기 순으로 선택하며 하나로 합치면 정렬된 배열을 얻을 수 있다.

[1, 2, 3, 4, 5, 6, 7, 8]

 

Python Code

def merge_sort(arr):
	def sort(low, high):
    	if high - low < 2:
        	return
        mid = (low + high) // 2
        sort(low, mid)
        sort(mid, high)
        merge(low, mid, high)
        
    def merge(low, mid, high):
    	temp = []
        l, h = low, mid
        
        while l < mid and h < high:
        	if arr[l] < arr[h]:
            	temp.append(arr[l])
            	l += 1
            else:
            	temp.append(arr[h])
                h += 1
        
        while l < mid:
        	temp.append(arr[l])
            l += 1
        while h < high:
        	temp.append(arr[h])
            h += 1
        
        for i in range(low, high):
        	arr[i] = temp[i - low]
    
    return sort(0, len(arr))

 

시간 복잡도

- 위의 예제와 같이  8 -> 4 -> 2 -> 1 식으로 전반적인 반복의 수는 절반씩 줄어들기 때문에 O(logN)의 시간이 필요하며, 각 단계에서 병합할 때 모든 값들을 비교해야 하므로 O(N)의 시간이 소모된다. 따라서 총 시간 복잡도는 O(NlogN)이다.

 

공간 복잡도

두개의 배열을 병합할 때 병합 결과를 담아 놓을 배열이 필요하므로 공간 복잡도는 O(N)이다.