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

오늘은 퀵 정렬(Quick sort)와 유사한 병합정렬(Merge Sort) 알고리즘에 대해 알아보겠습니다

병합정렬은 존 폰 노이만(John von Neumann) 1945년에 개발한 알고리즘인데요

해당 알고리즘은 비교정렬에 속하며 여러 비교정렬 알고리즘 중에 빠른 성능을 보이는 알고리즘입니답

 

# 동작과정 

병합정렬을 한문장으로 이렇게 표현할 수 있습니다! 

" 일단 반씩 계속 쪼개고 나중에 합침" 

 

퀵정렬과 유사하게 분할 정복(Divide and Conquer)의 방식으로 동작하는데욥 2단계로 세분화하여 살펴볼 수 있습니다

 

step1) 분할 

분할된 크기가 1이 될때까지 절반씩 분할합니다

 

step2) 병합 및 정렬

분할된 배열을 한 묶음이 될때까지 각각 병합하면서 정렬합니다

 

38, 27, 43, 3, 9, 82, 10을 오름차순으로 정렬 해보겠습니다!

2단계인 분할과 병합 및 정렬의 과정을 수행하며 정렬이 완료됩니다

 

# Python 코드

따로 병합을 저장할 추가적인 배열(sorted)을 만들어 정렬을 진행합니다!

배열 sorted -> 정렬된 결과를 임시로 저장하는 공간

배열 A -> 원본 입력 배열(여기서는 arr)

 

배열 A를 반으로 나눠 B, C 생성

배열 B -> 왼쪽 부분 배열 (left ~ mid)

배열 C -> 오른쪽 부분 배열 (mid+1 ~ right)

arr = [4, 2, 2, 8, 3, 3, 1] # 입력 배열 arr

sorted = [0] * len(arr)  # sorted 배열 초기화

def merge(A, left, mid, right):

    global sorted  # 병합을 위한 추가적인 배열

    k = left  # 배열 C(정렬될 리스트)의 인덱스

    i = left  # 배열 A의 인덱스

    j = mid + 1  # 배열 B의 인덱스

    # 분할 정렬된 리스트의 병합

    while i <= mid and j <= right:

        if A[i] <= A[j]:

            sorted[k] = A[i]  # 왼쪽 리스트의 값이 작으면 그 값을 선택

            i, k = i + 1, k + 1

        else:

            sorted[k] = A[j]  # 오른쪽 리스트의 값이 작으면 그 값을 선택

            j, k = j + 1, k + 1

    # 한쪽에 남아 있는 레코드의 일괄 복사

    if i > mid:  # 왼쪽 리스트가 먼저 소진된 경우

        sorted[k:k + right - j + 1] = A[j:right + 1]  # 오른쪽 리스트 복사

    else:  # 오른쪽 리스트가 먼저 소진된 경우

        sorted[k:k + mid - i + 1] = A[i:mid + 1]  # 왼쪽 리스트 복사

    A[left:right + 1] = sorted[left:right + 1]  # sorted를 원래 배열 A에 복사

def merge_sort(A, left, right):

    if left < right:  # 배열의 요소가 2개 이상인 경우에만 실행

        mid = (left + right) // 2  # 중간 지점 계산

        merge_sort(A, left, mid)  # 왼쪽 부분 배열 정렬

        merge_sort(A, mid + 1, right)  # 오른쪽 부분 배열 정렬

        merge(A, left, mid, right)  # 정렬된 두 부분 배열을 병합

    return A

print(merge_sort(arr, 0, len(arr)-1))

 

# 성능분석 - 시간복잡도

병합정렬은 퀵정렬과 마찬가지로 분할정복(Divide and Conquer)의 방식을 사용하지만, 퀵정렬과는 다르게 최악의 경우에도 O(nlogn)의 시간복잡도를 보장합니다!!

결론적으로 평균(Average), 최악(Worst), 최선(Best) 모두 O(nlogn)의 시간복잡도를 보이는데욥 

이는 데이터가 어떤상태(정렬되어 있든 반대로 정렬되어 있든)와는 상관없이 균등하게 분할하고 병합하여 정렬이 되기 때문입니다!

반면, 퀵정렬은 피벗(pivot) 기준값에 따라 분할이 달라지므로 항상 O(nlogn)의 시간복잡도를 보장하지 못합니다

 

정렬된 배열끼리 합치는 과정에서 최소 n번 비교 X logn 깊이로 분할되어 병합

= O(nlogn)

 

하지만 퀵정렬에 비해 단점이 있는데요

분할하며 정렬시 정렬된 결과를 저장할 추가적인 메모리가 필요합니다!! 

 

# reference

컴퓨터 알고리즘. (2006). 대한민국: 도서출판 홍릉(홍릉과학출판사).

Baase, S., Van Gelder, A. (1999). Computer Algorithms: Introduction to Design and Analysis, 3rd Edition. 인도: Addison-Wesley.

파이썬 자료구조와 알고리즘: for beginner. (2021). 대한민국: 한빛아카데미.