그냥 공부하다가 Python으로 Merge Sort를 구현해 보았다.


#!/usr/bin/env python3

def merge_sort(arr):
    if len(arr) < 2:
        return arr
    middle = len(arr) // 2
    left = merge_sort(arr[:middle])
    right = merge_sort(arr[middle:])
    merged = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    if len(left) == i:
        merged += right[j:]
    else:
        merged += left[i:]
    return merged


# 테스트 출력 코드
from random import shuffle

test_case = list(range(1, 101))
shuffle(test_case)
print('Before Sort :\n', test_case)
print('After Sort :\n', merge_sort(test_case))