병합 정렬

병합정렬(merge sort)은 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다. 

 

 

정렬을 마친 배열의 병합

 

쪼개진 두 배열이 정렬을 마친 후 병합하는 과정을 살펴본다. 각 배열에서 주목하는 원소의 값을 비교하여 작은 쪽의 원소를 꺼내 새로운 배열에 저장한다. 이 작업을 반복하며 정렬을 마친 배열을 만든다. 

 

 

<예제 code>

위의 코드는 3개의 반복문을 늘어놓는 단순한 병합 알고리즘이다. 병합하는 데 필요한 시간 복잡도는 O(n)이다.

def merge_sorted_list(a, b, c):
    pa, pb, pc = 0, 0, 0     # 각 배열의 커서(인덱스)
    na, nb, nc = len(a), len(b), len(c)    # 각 배열의 원소 수
    
    while pa < na and pb < nb:    # pa와 pb를 비교하여 더 작은 값을 pc에 저장
        if a[pa] <= b[pb]:
            c[pc] = a[pa]
            pa += 1
        else:
            c[pc] = b[pb]
            pb += 1
        pc += 1
        
    while pa < na:    # a에 남은 원소를 c에 복사 (남은 찌꺼기 c에 넣기)
        c[pc] = a[pa]
        pa += 1
        pc += 1
        
    while pb < nb:
        c[pc] = b[pb]
        pb += 1
        pc += 1
        
if __name__ == '__main__':
    a = [2, 4, 6, 8, 11, 13]
    b = [1, 2, 3, 4, 9, 16, 21]
    c = [None] * (len(a) + len(b))
    
    merge_sorted_list(a, b, c)
    
    print('배열 a와 b를 병합하여 배열 c에 저장했습니다.')
    print(f'배열 a : {a}')
    print(f'배열 b : {b}')
    print(f'배열 c : {c}')

 

 

 

 

c = list(sorted(a + b))

 

import heapq
c = list(heapq.merge(a, b))

 

파이썬의 내장함수인 sorted()를 통해 쉽게 적용할 수 있지만 속도가 상대적으로 느리다. 빠르게 병합하려면 heapq 모듈의 merge() 함수를 사용하면 된다.

 

 

 

병합 정렬 만들기

 

정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다. 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 뒤 병합하여 배열 정렬을 완료한다.

 

 

 

병합 정렬 알고리즘의 순서는 다음과 같이 정리할 수 있다.

배열의 원소 수가 2개 이상인 경우 1. 배열의 앞부분을 병합 정렬로 정렬한다. 2. 배열의 뒷부분을 병합 정렬로 정렬한다. 3. 배열의 앞부분과 뒷부분을 병합한다.

 

<code>

from typing import MutableSequence

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                    # 작업용 배열을 소멸

if __name__ == '__main__':
    print('병합 정렬을 수행합니다')
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num    # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    merge_sort(x)       # 배열 x를 병합 정렬

    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

 

 

배열 병합의 시간 복잡도는 O(n)이다. 데이터 원소 수가 n일 때 병합 정렬의 단계는 log n만큼 필요하므로 전체 시간 복잡도는 O(n log n)이다. 병합 정렬 알고리즘은 서로 떨어져 있는 원소를 교환하는 것이 아니므로 안정적이다.