병합 정렬

병합 정렬

 

배열을 앞부분 A 배열과 뒷부분 B 배열의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘입니다. 

각 배열에서 주목하는 원소의 값을 비교하여 작은 쪽의 원소를 꺼내 새로운 배열 C에 저장합니다.

 

정렬을 마친 두 A, B 배열을 병합하는 코드입니다.

def merge_sorted_list(a: Sequence, b: Sequence, c: MutableSequence) -> None:
    """정렬을 마친 배열 a와 b를 병합하여 c에 저장"""
    pa, pb, pc = 0, 0, 0
    na, nb, nc = len(a), len(b), len(c)

    while pa < na and pb < nb:
        if a[pa] < b[pb]:
            c[pc] = a[pa]
            pa += 1
        else:
            c[pc] = b[pb]
            pb += 1
        pc += 1

    # 배열 b의 모든 원소를 배열 c에 복사했지만,배열 a에 아직 원소가 남았다면
    while pa < na:
        c[pc] = a[pa]
        pa += 1
        pc += 1
        
    # 배열 a의 모든 원소를 배열 c에 복사했지만,배열 b에 아직 원소가 남았다면
    while pb < nb:
        c[pc] = b[pb]
        pb += 1
        pc += 1

 

이때 파이썬에서 제공하는 sorted() 함수를 사용하면 다음과 같이 병합할 수 있습니다. 

c = list(sorted(a + b))

 

이 방법은 a와 b가 정렬을 마친 상태가 아니더라도 적용할 수 있지만, 속도가 느립니다. 빠르게 병합하려면 다음과 같이 heapq 모듈의 merge() 함수를 사용하면 됩니다.

import heapq

a = [2, 4, 5, 6, 10]
b = [1, 3, 7, 8]
c = list(heapq.merge(a,b))

 

병합 정렬 만들기

 

def merge_sort(a: MutableSequence) -> None:
    """병합 정렬"""

    def _merge_sort(a: MutableSequence, left: int, right: int) -> None:
        """a[left] ~ a[right]를 재귀적으로 병합 정렬"""
        if left < right:
            center = (left + right) // 2

            _merge_sort(a, left, center)            # 배열 앞부분을 병합 정렬
            _merge_sort(a, center + 1, right)       # 배열 뒷부분을 병합 정렬

            p = j = 0
            i = k = left

            while i <= center:
                 buff[p] = a[i]
                 p += 1
                 i += 1

            while i <= right and j < p:
                 if buff[j] <= a[i]:
                     a[k] = buff[j]
                     j += 1
                 else:
                     a[k] = a[i]
                     i += 1
                 k += 1

            while j < p:
                a[k] = buff[j]
                k += 1
                j += 1

    n = len(a)
    buff = [None] * n           # 작업용 배열을 생성
    _merge_sort(a, 0, n - 1)    # 배열 전체를 병합 정렬
    del buff                    # 작업용 배열을 소멸