[탐색과 정렬] 병합 정렬

병합 정렬 (Merge Sort)

비교 기반 정렬 알고리즘

분할 정복(Divide And Conquer) 알고리즘의 하나

분할 정복 (Divide And Conquer)
큰 문제를 작은 문제로 나눠서(분할하여) 해결하는(정복하는) 방법
입력 크기가 큰 문제도 작게 나누는 것을 반복하면 쉬운 문제, 즉 종료 조건이 되는 원리 이용

 

정렬 방법

1. 리스트의 길이가 0 또는 1이면 정렬된 상태로 판단한다.
2. 리스트가 정렬되지 않았으면, 반으로 나눠 부분 리스트를 생성한다.
3. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.
4. 정렬된 리스트를 하나의 리스트로 병합한다.

이미지 출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

계산 복잡도는 $$ O(n\log{n}) $$

 

코드

def merge_sort(list):
    n = len(list)
    
    # 종료 조건
    if n <= 1:
        return
        
    # 정렬
    mid = n // 2 # 리스트의 절반 계산
    front = list[:mid] # 부분 리스트 생성
    back = list[mid:]
    
    # 재귀 호출
    merge_sort(front)
    merge_sort(back)

    # 병합
    f = 0
    b = 0
    l = 0
    while f < len(front) and b < len(back):
        if front[f] < back[b]:
            list[l] = front[f]
            f += 1
            l += 1
        else:
            list[l] = back[b]
            b += 1
            l += 1
        print(list)

    # 남은 리스트 복사
    while f < len(front):
        list[l] = front[f]
        f += 1
        l += 1
    while b < len(back):
        list[l] = back[b]
        b += 1
        l += 1