병합 정렬(Merge Sort) 알고리즘

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

병합 정렬(Merge Sort)?

주어진 배열을 더 이상 분할할 수 없는 수준까지 분할한 뒤 분할된 원소들을 정렬하여 재조합하는 정렬 알고리즘이다. 분할 정복 알고리즘을 사용한다.(작은 문제로 분리 후 각각에 대해 해결한 뒤 결과를 취합하여 기존 문제를 해결하는 알고리즘)

병합 정렬 동작

병합 정렬은 다음의 과정으로 진행된다.

1. 입력 받은 배열을 절반 기준으로 나눠서 분할된 배열에 대해 재귀적으로 함수를 호출한다.
2. 리스트의 길이가 0 or 1이면 그 자체로 정렬된 배열이므로 리턴한다.(재귀호출 종료)
3. 절반을 기준으로 나눠진 두 배열을 기준으로 정렬하여 리턴한다.(분할된 문제 해결 후 기존 문제 복귀)
4. 마지막으로 정렬된 배열이 반환된다.

결국 정렬된 배열 반환 과정은 다음의 3단계로 구성된다.

• 분할(Divide) : 입력 배열을 절반 기준으로 2개의 부분 배열로 분할
• 정복(Conquer) : 부분 배열을 정렬, 부분 배열이 아직 덜 분할되었다면 재귀호출하여 분할 진행
• 결합(Combine) : 반환된 두 부분 배열을 하나의 배열로 병합

위 과정에 따라 몇 가지 특성을 갖게 된다.

• 절반씩 나누는 과정에서 $log\ n$, 전체 정렬 과정에서 $cn$만큼 소요된다고 하면 정렬 알고리즘의 시간복잡도는 최선, 최악의 구분 없이 $O(nlog\ n)$이다.
• 추가 배열을 생성하여 병합하기 때문에 메모리 소모가 크다.
• 중복된 값이 있을 때 그 순서가 바뀌지 않는 안정된 정렬(Stable)이다.

위 배열을 정렬한다고 할 때 전체 정렬 과정은 다음과 같다.

위의 방식처럼 앞에서 하나씩 뽑아서 더하는 방식으로 많이 설명한다. 그러나 이 방법은 deque자료형처럼 popleft를 지원하지 않으면 좌표 재배열을 거치기 때문에 연산량이 급격히 늘어난다.(사실상 $n^2$) 따라서, 배열이 아니라 좌표를 기준으로 표기만 해주면 연산량 문제가 해결된다.

위 그림처럼 좌표 기준으로 배열을 합치면 relocate 과정 없이 시간복잡도 $O(n)$으로 해결할 수 있다.

python 코드

def mergesort(arr):
    def merge(left, right):
        result = []
        l, r = 0, 0 # 부분 배열 커서
        while l < len(left) or r < len(right): # 커서들이 아직 값에 위치
            if l < len(left) and r < len(right): # 둘 다 유효하면
                if left[l] <= right[r]:
                    result.append(left[l])
                    l += 1 # 좌측 배열 원소 추가했으므로 커서 전진
                else:
                    result.append(right[r])
                    r += 1 # 우측 배열 원소 추가했으므로 커서 전진
            elif l < len(left): # right 배열 탐색이 끝났으면
                while l < len(left): # 나머지 left 전부 추가
                    result.append(left[l])
                    l += 1
            elif r < len(right): # left 배열 탐색이 끝났으면
                while r < len(right): # 나머지 right 전부 추가
                    result.append(right[r])
                    r += 1
        return result
    if len(arr) <= 1: # 배열의 길이가 1 이하면 그대로 반환
        return arr 
    mid = len(arr) // 2 # 절반을 기준으로
    left_list = mergesort(list(arr[:mid])) # 좌측 재귀호출
    right_list = mergesort(list(arr[mid:])) # 우측 재귀호출
    return merge(left_list, right_list) # 병합 후 리턴

a = [3, 1, 2, 5, 4, 6]
b = [6, 5, 4, 3, 2, 1]
c = [5, 5, 3, 3, 1, 1]
print(f'merge a:{mergesort(a)}, b:{mergesort(b)}, c:{mergesort(c)}')