[알고리즘] 병합 정렬(Merge Sort)에 대해서

예전에 대학교 2학년 과정에서 파이썬에 대한 수업을 들었을 때, 이 정렬 방법에 대해 처음 알았다.

 

교수님이 파이썬으로 병합 정렬을 구현하는 것을 과제로 내주셨는데, 병합 정렬이라는 개념을 잘 몰랐던 나는 많이 힘들게 과제를 결국 풀이 했던 것으로 기억이 난다.

 

교수님은 분할 정복을 병합 정렬을 통해 알려주고, 그것을 파이썬으로 최적화하여 학생들에게 파이썬에 대한 이해도를 높이려고 했던 것 같다. 하지만 기본적인 파이썬 문법들과 함수들을 응용하여 활용한다는 것이 파이썬을 갓 배운 학생들에게는 조금 어려웠던 과제였다고 생각한다.

 

하지만 이 과정속에서 깨닫는 과정이 너무 재미있었기 때문에 다시 알아두자는 의미로 이 글을 쓰게 되었다.

 

 

병합 정렬이란?

병합 정렬은 서론에 말했듯이 분할 정복 전략을 이용하여, 보통 재귀적으로 부분으로 나눈 뒤, 각각의 부분을 정렬하고 다시 병합하여 전체를 정렬하는 방식이다.

 

간단하게 2단계로 나눌 수 있다.

 

1. 분할

 

정렬해야 하는 리스트를 반으로 나눈다. 이 과정을 반복하여 해당 리스트의 크기가 1이 될 때까지 나눈다. 아까 서술했듯이 각각의 부분을 정렬하고 전체를 정렬하는 방식이라고 했는데, 크기가 1인 상태의 리스트는 이미 정렬된 상태라고 볼 수 있기 때문에 여기서 부터 시작한다.

 

2. 병합

 

나누어진 리스트들을 차례대로 병합해 나간다. 두 개의 정렬된 리스트를 합칠 때 각 리스트의 첫 번째 값부터 비교하여 작은 값을 앞에 배치하는 방식으로 정렬한다.

 

재귀적으로 처리하면 각각의 부분들이 계속해서 합쳐져 나가는데 그럼 최종적으로 하나의 리스트가 된다. 그러면 정렬이 된 것이다.

 

다음의 예시 그림으로 눈으로 확인해보자

 

 

최초의 리스트 [38, 27, 43, 1, 3, 9, 82, 10] 이 있다고 하자. 그 리스트를 절반씩 각각의 조각으로 분할한다. 그러면 리스트의 크기가 각각 1인 리스트가 되어버린다. 그리고 이 크기가 1인 리스트는 원소가 하나이기 때문에 정렬되어 있다고 볼 수 있다.

 

이제 각각의 리스트들을 병합하여 정렬한다. 각각의 리스트들은 병합 직전에 항상 정렬된 상태를 유지한다고 볼 수 있다. 최종적으로 모두 병합하게 되면 정렬된 리스트가 나타나게 된다.

 

 

어떤 특징을 가질까?

 

병합 정렬이 가지는 가장 큰 특징은 시간복잡도가 최악이든 최선이든 O(n log n) 의 시간을 가지기 때문에 매우 일정한 성능을 가지고 있다고 볼 수 있다. 다른 예시로 퀵 정렬 같은 경우에는 최악의 경우 성능이 매우 떨어질 수도 있기 때문이다.

 

그리고 계속해서 작은 부분끼리의 정렬된 부분을 가지고 합친다는 점에서 안정성이 있다. 그래서 상대적인 순서를 유지하기 때문에 병합 정렬은 안정 정렬인데, 데이터 내 특정 필드가 같을 때 그 외 다른 필드에 따라 추가적인 정보나 정렬이 의미를 가질 수 있는 경우 활용하면 좋다.

 

하지만 병합하는 과정에서 추가 메모리 공간이 필요하다. 사실상 별도의 리스트에 두 리스트를 병합하기 때문에 추가적인 메모리 공간을 요한다. 이러한 방식 때문에 원본 리스트에서 새로운 리스트를 만들어서 정렬하는 것과 다름 없기 때문에 메모리 효율성도 떨어진다.

 

 

파이썬으로 구현

이제 어떤 방식으로 병합 정렬을 하는지 알아보았으니 이제 파이썬으로 구현해보자

 

def merge_sort(nums):
    if len(nums) > 1:
        mid = len(nums) // 2
        left = nums[:mid]
        right = nums[mid:]

        merge_sort(left)
        merge_sort(right)

        i = 0
        j = 0
        k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                nums[k] = left[i]
                i += 1
            else:
                nums[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            nums[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            nums[k] = right[j]
            j += 1
            k += 1

 

해당 코드에서는 일단 들어온 리스트의 길이가 1 이상이면 재귀적으로 계속 호출을 해서 절반으로 쪼갠다. 그 후에 각각의 리스트들이 크기가 1로 쪼개졌다면 left 와 right 의 값이 크기가 1인 리스트일 것이다.

 

이 두 리스트의 원소들의 크기를 비교하여 정렬된 리스트를 계속해서 만들어 병합해 나가면 최종적으로 정렬하려는 리스트는 정렬이 된다. 아래의 코드들은 남은 요소들을 집어넣기 위함인데 이미 모든 부분부분의 리스트들은 정렬이 되어 있으므로 남은 요소가 있다면 그것은 k 인덱스 위치에 그대로 넣어주면 될 것이기 때문에 이렇게 처리하였다.

 

num_list = [38, 27, 43, 1, 3, 9, 82, 10]

merge_sort(num_list)

print(num_list)

[1, 3, 9, 10, 27, 38, 43, 82]

 

예시 그림의 데이터를 그대로 넣고 돌려본 결과 제대로 병합 정렬이 되었음을 알 수가 있다.

 

 

정리

병합 정렬은 안정 정렬이며, 정렬 하고자 하는 리스트를 분할 정복 전략을 사용하여 병합해 나가는 정렬 방법이다.

 

시간복잡도도 최악의 경우와 최선일 경우에 모두 같기 때문에 매우 일정한 성능을 가지고 있는 정렬 알고리즘이다.

 

사실 이 병합 정렬을 다루게 된 이유는 작성자의 대학 생활이 계기가 되었지만 궁극적으로는 파이썬에서 사용하는 sort() 와 sorted() 에서 사용되는 정렬 방식인 Timsort 에 대해서 차차 다루고 싶어서 일단 병합 정렬에 대해 알아보았다.

 

Timsort 는 병합 정렬과 삽입 정렬(insertion sort) 를 결합한 하이브리드 정렬 방식이기 때문에 삽입 정렬에 대해 더 알아본 다음에 Timsort 에 대해 알아볼 것 같다.

 

 

참고:

문제 해결력을 높이는 알고리즘과 자료구조

문제 해결력을 높이는 알고리즘과 자료 구조 - 예스24 (yes24.com)  

Hello Coding 그림으로 개념을 이해하는 알고리즘

Hello Coding 그림으로 개념을 이해하는 알고리즘 - 예스24 (yes24.com)