병합 정렬(Merge Sort) - 복습필요

병합 정렬(Merge Sort)

• 분할 정복 알고리즘의 기법을 사용하는 정렬 알고리즘 중 하나
  (분할 정복 알고리즘의 대표적인 예 중 하나기도 하다.)
• 데이터를 잘게 쪼개 정렬한다.
• Memoization을 사용하지 않음
• 재귀 용법을 활용

사용방법

1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
2. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.
3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다.

 

구현

재귀 용법으로 데이터를 나누는 함수, 나눠진 데이터를 병합하는 함수

두 단계를 함수로 만들어 사용

 

def merge_sort(data):
    return split(data)

def split(data):
    if len(data) <= 1:
        return data
    medium = int(len(data) / 2)
    left = split(data[:medium])
    right = split(data[medium:])
    return merge(left, right)

def merge(left, right):
    merged = []
    lp, rp = 0, 0

    # Case 1. left/right 둘 다 아직 남아있을 때
    while len(left) > lp and len(right) > rp:
        if left[lp] > right[rp]:
            merged.append(right[rp])
            rp += 1
        else:
            merged.append(left[lp])
            lp += 1

    # Case 2. left만 남아있을 때
    while len(left) > lp:
        merged.append(left[lp])
        lp += 1

    # Case 3. right만 남아있을 때
    while len(right) > rp:
        merged.append(right[rp])
        rp += 1
    
    return merged

import random
data_list = random.sample(range(100), 10)
print(merge_sort(data_list))

 

분석

한 단계(depth)에 대해 

각 노드의 계산양: n / 2ⁱ

노드 개수: 2ⁱ

즉, 각 단계는 항상 O(n)의 시간복잡도를 가진다.

 

단계는 항상 log₂n개 만큼 만들어지므로 상수 떼고

단계가 만들어지는 시간복잡도는 O(log n)

 

따라서, 총 시간복잡도는 O(n) * O(log n) = O(n log n)이 된다.