합병 정렬(Merge Sort) [Python / 파이썬]

-목차-

1. 합병 정렬(Merge Sort)

2. 합병 정렬의 시간 복잡도

3. 합병 정렬의 특성

1. 합병 정렬(Merge Sort)

합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.

 

합병 정렬은 아래와 같은 알고리즘으로 동작한다.

• 배열을 원소가 하나밖에 남지 않을 때까지 계속 둘로 쪼갠다.
• 더 이상 쪼갤 수 없는 각각의 배열을 합병하며 정렬한다 이때 크기 순으로 재배열하며 힙병이 이루어진다.

이해를 돕기 위해 예제를 통해 자세한 동작 원리를 알아보자.

예를 들어, 아래와 같이 1부터 8까지 총 8개의 숫자가 들어있는 배열에 있다고 가정해보자.

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

 

먼저 하나의 배열을 둘로 쪼갠다.

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

 

그리고 다시 두 개의 배열을 넷으로 쪼갠다.

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

 

마지막으로 네 개의 배열을 여덜개로 쪼갠다.

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

 

이제 더 이상 쪼갤 수가 없으니 두열을 병합한다. 병합할 때는 작은 숫자가 앞에 큰 수자를 뒤에 위치시키도록 한다.

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

 

이제 4개의 배열을 2개로 병합한다. 각 배열 내에서 가장 작은 값 2개를 비교해서 더 작은 값을 먼저 선택하면 자연스럽게 크기 순으로 선택이 된다.

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

 

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

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

 

재귀를 이용해서 병합 정렬을 구현할 수 있다. 먼저 배열을 더 이상 나눌 수 없을 때까지 (원소가 하나만 남을 때까지) 최대한 분할 후에, 다시 병합하면서 점점 큰 배열을 만들어 나가면 된다. 파이썬의 리스트 slice notation(arr[start:end])을 사용하면 다음과 같이 간결한 코드를 작성할 수 있다.

def merge_sort(arr):
    if len(arr) < 2:
        return arr
    
    # 하나의 원소만 남도록 배열을 둘로 쪼개는 과정
    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    # 정렬된 원소를 저장할 배열 선언
    merged_arr = []
    
    # 왼쪽 오른쪽 배열의 포인터 정의
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        
        # 왼쪽 배열의 원소보다 오른쪽 배열의 원소가 크다면 왼쪽 배열의 원소를 추가하고 왼쪽 배열의 포인터 1증가
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
            
        # 오른쪽 배열의 원소보다 왼쪽 배열의 원소가 크다면 오른쪽 배열의 원소를 추가하고 오른쪽 배열의 포인터 1증가
        else:
            merged_arr.append(high_arr[h])
            h += 1
            
    # 한쪽 배열의 원소가 없다면 다른 한쪽의 배열은 이미 정렬되어 있는 상태이므로 배열의 값을 그대로 추가
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr

arr = [6, 5, 3, 1, 8, 7, 2, 4]
merge_sort(arr)

 

---

2. 합병 정렬의 시간 복잡도

• 예제에서 보이는 것과 같이 8 -> 4 -> 2 -> 1 식으로 전반적인 반복의 수는 점점 절반으로 줄어들 기 때문에 O(logN) 시간이 필요하며, 각 패스에서 병합할 때 모든 값들을 비교해야 하므로 O(N) 시간이 소모된다. 따라서 총 시간 복잡도는 O(NlogN)이다.
• 두 개의 배열을 병합할 때 병합 결과를 담아 놓을 배열이 추가로 필요하므로 공간 복잡도는 O(N)이다.
• 다른 정렬 알고리즘과 달리 인접한 값들 간에 상호 자리 교대(swap)가 일어나지 않는다.

 

---

3. 합병 정렬의 특성

합병 정렬은 수행 과정에서 리스트를 쪼갰다가 다시 합치는데, 같은 숫자의 경우에는 순서가 뒤바뀌지 않으므로 stable sort이다. 별도 저장 공간이 필요한지 여부(in-place sort 여부)는 자료구조를 뭘 쓰느냐에 따라 달라진다.

우선 연결 리스트(linked list)를 쓰는 경우엔 in-place sort로 구현할 수 있다. 다음과 같이 기존 저장공간에서 포인터만 바꾸는 형식으로 합병 정렬을 수행할 수 있는 덕분이다. 예컨대 데이터를 쪼갤 경우 head 포인터를 더 두면 되고, 정렬하려는 경우 next 포인터가 가리키는 주소 값을 바꿔주면 된다.

 

 

반면 배열을 쓰는 경우에는 다음 그림처럼 정렬된 리스트를 저장해 둘 별도 공간(buffer)이 필요해 in-place sort가 아니게 된다.

 

 

---

참고 자료

https://www.daleseo.com/sort-merge/

https://ratsgo.github.io/data%20structure&algorithm/2017/10/03/mergesort/

https://ko.wikipedia.org/wiki/합병정렬