9장 병합 정렬(Merge Sort)[PYTHON]

목차
1. 병합 정렬
2. 그림으로 이해
3. 코드
4. 느낀점

병합 정렬

병합 정렬은 분할 정복 기법을 사용한 정렬 알고리즘이다.
리스트를 1개의 리스트가 될 때까지 분할하는 과정과 병합하는 과정으로 이루어진다.
시간 복잡도는 O(nlogn)으로 다른 정렬에 비해 효율성이 좋다.

그림으로 이해

아래와 같은 데이터가 담긴 리스트가 있다고 가정하자.
병합 정렬을 이용하여 오름차순으로 정렬하자.

일단 이 리스트를 가장 잘게 쪼개면 다음과 같이 된다.

그 후 쪼갠 부분끼리 병합을 진행한다.
아래와 같은 상황에서는 파란색 부분이 병합되는 부분이다.
병합할 때 오름차순으로 정렬해야한다.

한번 병합을 진행하게 되면 아래와 같이 분할된 부분은 8 -> 4로 바뀌게 되며 각 부분은 병합이 되면서 오름차순으로 정렬된 모습을 확인할 수 있다.

이 과정을 반복하면 정렬이 된다.
우리는 이런 알고리즘을 병합 정렬 알고리즘이라고 부른다.

병합할 때 작동하는 원리는 다음과 같다.

• 병합 하려는 양쪽을 투포인터로 양쪽의 처음 포인트를 잡는다.
• 새로운 병합 리스트를 만들어 순서대로 넣어준다.
• 최종적으로 반환하여 준다.

코드

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

def merge_sort(num):
    def sort(s, e):
        if e - s <= 1:
            return
        mid = (s + e) // 2
        sort(s, mid)
        sort(mid, e)
        merge(s, mid, e)

    def merge(s, mid, e):
        temp = []
        l = s
        m = mid
        while l < mid and m < e:
            if num[l] > num[m]:
                temp.append(num[m])
                m += 1
            else:
                temp.append(num[l])
                l += 1

        while  l < mid:
            temp.append(num[l])
            l += 1
        while  m < e:
            temp.append(num[m])
            m += 1
        for i in range(s, e):
            num[i] = temp[i - s]
    return sort(0, len(num))

merge_sort(num)
print(num)

느낀점

병합 정렬에 대해서 공부해봤는데 퀵정렬과 마찬가지로 정렬 알고리즘중 가장 어려웠던 개념같다.
하지만 코딩 테스트에서 자주 활용되는 알고리즘이 있기에 잘 숙지해두자.

참고한 자료 : 링크텍스트, DO IT 알고리즘 코딩테스트 - 김종관