병합정렬

병합정렬은 기초적인 정렬 알고리듬 중에서 널리 알려진 알고리듬 중 하나이며, 대표적인 분정복 알고리듬의 예인 동시에 재귀 알고리듬의 좋은 예이다. 이름에 ‘병합'(merge)이 들어가는 이유는 배열을 2개 혹은 그 이상의 작은 조각으로 나누고 각각의 조각을 정렬한 다음, 각 조각의 앞에서부터 가장 작은 값을 순서대로 골라서 정렬된 결과를 생성하기 때문이다.

원래의 배열을 쪼갠 각각의 조각 역시 똑같은 병합 정렬을 이용해서 정렬하는 재귀적인 동작을 수행한다. 재귀적 알고리듬의 수행 과정을 복잡하고 어렵게 여기는 사람들이 있는데, 입력과 결과에 집중하는 방식으로 바라보면 오히려 더욱 명료하고 간단하다는 것을 알 수 있다.

예시를 이용해서 병합정렬이 어떤식으로 동작하는지 살펴보자. 아래와 같은 배열을 정렬하여 정렬된 사본을 만들 것이다.

[45][53][26][93][62][20][33][17]  -> [  ][  ][  ][  ][  ][  ][  ][  ]

가운데를 기준으로 리스트를 두 개로 나누고, 각각을 정렬하면 다음과 같은 결과를 얻게 된다. 여기서 각 배열을 편의상 left, right 라고 부르겠다.

: left             : right 
[26][45][53][93] + [17][20][33][62]
 
-> [  ][  ][  ][  ][  ][  ][  ][  ]

각 배열의 첫번째 값을 서로 비교한다. 26과 17인데 그 중에 작은 17을 채택하여 결과 리스트에 맨 앞에 담는다.

: left             : right 
[26][45][53][93] + [##][20][33][62]
 
-> [17][  ][  ][  ][  ][  ][  ][  ]

left에 대해서는 아직 첫 원소를 봐야하고, right에 대해서는 이제 두번째 원소를 본다. 여전히 right 쪽의 값이 더 작다.

: left             : right 
[26][45][53][93] + [##][##][33][62]
...
[##][##][##][93] + [##][##][##][##]
 
-> [17][20][26][33][45][53][62][  ]

이런식으로 정렬된 부분열에서 최소값을 찾아 더하는 동작을 반복해나가면 right의 모든 원소가 결과에 들어가게 된다. 그러면 반대쪽 배열에 남은 원소들은 정렬된 상태로 남아있기 때문에 순서대로 결과에 추가해주면 된다.

: left             : right 
[##][##][##][93] + [##][##][##][##]
 
-> [17][20][26][33][45][53][62][  ]

이제 실제 알고리듬을 정리해보자.

  1. 입력으로 받은 리스트의 길이가 2 이하라면 정렬할 필요가 없는, 정렬된 상태로 본다. 이 경우 원본을 그대로 리턴한다.
  2. 길이가 2 이상이라면 길이의 절반값을 기준으로 자른 두 리스트를 각각 병합 정렬하고 이를 left, right라고 이름 짓는다.
  3. left, right에서 각각 비교할 값을 가리킬 인덱스 l, r을 정의하고 0으로 초기화한다.
  4. 결과값이 될 빈 리스트를 생성한다.
  5. left[l]right[r] 중에서 작은 값을 찾는다. 작은 값을 결과에 추가하고, 그 값을 가리킨 인덱스를 1 증가시킨다.
  6. left, right 중에서 각자의 인덱스가 배열의 범위를 벗어날 때까지 5를 반복한다.
  7. left, right 중에서 원소가 남아있는 (인덱스가 배열 내부에 있는) 배열의 남은 원소를 모두 결과에 추가한다.
  8. 결과를 리턴한다.

병합 정렬은 재귀 함수로 구현되므로 종료조건을 반드시 설정해야 하고, 이 때 위 1번 규칙이 종료 조건에 해당한다. 이를 코드로 옮기면 다음과 같다.

from typing import List, TypeVar

# 임의의 타입 T를 정의한다.
T = TypeVar('T')


def merge_sort(xs: List[T]) -> List[T]:
    mid = len(xs) // 2
    # 길이가 0, 1이면 mid == 0 이다.
    if mid == 0:
        return xs
        
    # 결과준비, left, right 준비
    res = []
    left = merge_sort(xs[:mid])
    right = merge_sort(xs[mid:])
    l, r = 0, 0
    
    # 각 조각 배열을 병합하기
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            res.append(left[l])
            l += 1
        else:
            res.append(right[r])
            r += 1
    
    # 남아있는 조각을 마저 병합한다.
    while l < len(left):
        res.append(left[l])
        l += 1
    while r < len(right):
        res.append(right[r])
        r += 1
    
    return res

병합을 하는 과정에서 left, right의 추가되지 않은 최소값을 가리키는 인자를 조작하면서 움직이기 때문에 left, right, l, r 만 바뀌고 똑같은 코드가 계속 반복되는 부분이 별로 마음에 들지 않는다. 또한 이 코드는 위 ‘일반적인’ 알고리듬을 파이썬 코드로 옮겨 쓴 것이기 때문에 C나 다른 언어로 쓸 코드를 그대로 파이썬으로 옮겨놓은, 이른바 “파이썬으로 작성한 C 코드”같다.

살짝 생각을 바꿔보자. left, right는 이미 정렬된 리스트이다. 그래서 둘 모두 첫번째 값이 최소값이다. 두 리스트 중에서 최소값이 더 작은 리스트에서 “최소값을 떼어내어” 결과에 넣어준다면 어떻게 될까? 그 다음에도 똑같이 두 리스트에서 맨 앞의 원소들만 비교하면 된다.

이 방식으로 하나의 리스트를 소진했다면, 다른 리스트는 그대로 결과값에 들어가면 된다. 다른 리스트의 모든 원소를 append 하는 동작은 파이썬 리스트의 extend() 메소드이다.

이 아이디어를 바탕으로 위 코드를 좀 더 파이썬 코드 같이 바꿔보자.

def merge_sort_v(xs: List[T]) -> List[T]:
    mid = len(xs) // 2
    if mid == 0:
        return xs
    left, right = merge_sort_v(xs[:mid]), merge_sort_v(xs[mid:])
    right = 
    res = [], 0, 0
    
    while left and right:
        res.append((left if left else right).pop(0))
    res.extend((left if left else right))
    return res

리스트는 그 자체로 if, while 문에서 평가할 때 비어있으면 False, 원소가 하나라도 있으면 True가 되기 때문에 반복적으로 len()을 호출할 필요도, 인덱스를 따로 관리할 필요도 없다. 이런식으로 좀 더 간단한 코드로 정리된다.

심지어 실행 속도도 이 쪽이 근소하게 앞서는 것을 볼 수 있다. (다만 이 차이는 extend()를 사용하면서 루프를 줄인 데서 비롯하는 것으로 매우 근소한 수준이며, 부분 배열이 연속된 값을 얼마나 포함하느냐 등에 따라서 반대의 결과가 나올 수도 있을 것 같다..)

%timeit merge_sort(xs)
7.72 ms ± 125 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)


%timeit merge_sort_v(xs)
6.38 ms ± 147 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

병합정렬 자체도 재귀함수로 만들어져 있는데, 재귀가 나온 김에 병합 하는 과정 자체를 재귀로 작성해보도록 하자. 병합 함수를 따로 작성한다면 res, left, right를 모두 인자로 받아서 병합된 결과를 리턴하면 된다. left, right 중 빈 배열이 있다면 비어있지 않은 쪽을 res에 연결해서 리턴한다. 둘 다 비어있지 않다면 res 에 최소값을 연결한 것과, 최소값을 뗀 나머지 배열들을 인자로 해서 재귀 호출을 하면 된다. 먼저 병합 헬퍼 함수는 다음과 같이 작성된다.

def merge_helper(xs, left, right) -> List[T]:
    if not (left and right):
        return xs + (left if left else right)
    if left[0] < right[0]:
        return merge_helper(xs + left[:1], left[1:], right)
    return merge_helper(xs + right[:1], left, right[1:])

병합 정렬 함수는 같은 식으로 left, right를 만든다음, 병합 헬퍼 함수에 전달하여 최종 결과를 만들어 리턴한다.

def merge_sort_w(xs: List[T]) -> List[T]:
    mid = len(xs) // 2
    left = merge_sort_w(xs[:mid])
    right = merge_sort_w(xs[mid:])
    return helper([], left, right)

병합 정렬 함수 내에서는 leftright를 재귀 호출로 구한 후 이를 가공해서 결과를 만들었다. 하지만 병합 헬퍼 함수인 merge_helper()는 기저 케이스를 제외하면 return merge_helper( ... ) 의 형태가 된다. 이렇게 재귀호출한 결과를 그대로 리턴하는 재귀 함수의 형태를 꼬리 재귀라 한다. 파이썬에서는 이 꼬리 재귀가 특별한 의미를 가지지 않지만, 꼬리 재귀는 내부적으로 반복문으로 변경하여 함수 호출에 들어가는 비용을 없애기 유리하다. 실제로 많은 컴파일러들이 꼬리 재귀 형태로 작성된 코드를 반복문으로 바꿔서 최적화한다. 하지만 파이썬은 꼬리 재귀 최적화를 지원하지 않기 때문에 이런식으로 작성할 수도 있다… 정도로 참고하면 되겠다.