[Python3] Merge Sort (병합 정렬)

그냥 공부하다가 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))

2018-07-22 추가 :

위 방식과 다르게 원본 list(array)를 in-place 정렬하는 방식으로 다시 작성해 보았다

#!/usr/bin/env python3

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


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

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

2018-08-06 추가 :

위 방식에 여전히 비효율적인 부분이 있어, 임시 배열을 완성후 교체하는 것이 아니라 임시 배열을 읽으며 원본을 수정하는 방식으로 변경해 보았다.

#!/usr/bin/env python3


def merge_sort(arr, left, right):
    if right - left < 2:
        return
    merge_sort(arr, left, (left+right)//2)
    merge_sort(arr, (left+right)//2, right)
    temp_arr = arr[left:right]
    i, j, k = 0, len(temp_arr)//2, left
    while i < len(temp_arr)//2 and j < len(temp_arr):
        if temp_arr[i] > temp_arr[j]:
            arr[k] = temp_arr[j]
            j += 1
        else:
            arr[k] = temp_arr[i]
            i += 1
        k += 1
    if j == len(temp_arr):
        arr[k:right] = temp_arr[i:len(temp_arr)//2]



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

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