Merge sort by python

개념

이미지 출처

하나의 리스트를 잘게 쪼개어 divide(분할)한 후 이들을 Conquer(정렬)하여 combine(결합)하는 과정을 반복한다.

구현

1. Divide

def merge_sort(v):
    if len(v) <= 1:
        return v
    m = len(v) // 2
    left = merge_sort(v[:m])
    right = merge_sort(v[m:])
    return merge(left, right)

원소가 하나만 남을 때까지 recursive 로 입력된 list를 분할하고, 이들을 conquer, combine 해준 list를 return 한다.

2. Conquer and Combine

입력받은 두 개의 리스트를 합쳐 오름차순으로 정렬한 후 return 해준다.

def merge(left, right):
    res = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    if i < len(left):
        res.extend(left[i:])
    elif j < len(right):
        res.extend(right[j:])
    return res