파이썬, 합병 정렬(병합 정렬, 머지 소트, Merge Sort)

폰 노이만 선생님이 만드신 합병 정렬. 

퀵 소트와 같이 분할 정복 알고리듬을 사용합니다. 

퀵 소트와는 달리 안정 정렬입니다. 

 

안경잡이 개발자님이 설명을 잘해주셨네요.
좋아요 한번 누르고 나왔습니다. 

https://blog.naver.com/ndb796/221227934987

위키백과에 올라와 있는 gif

설명대로 코딩해 보았습니다. 

# merge sort 2020-10-12
# https://comdoc.tistory.com

def merge_sort(nums):
    if len(nums) < 2:
        return nums
    center = len(nums) // 2
    left, right = nums[:center], nums[center:]
    return merge(merge_sort(left), merge_sort(right))


def merge(left: list, right: list):
    left_index = right_index = 0
    merged = []
    left_length, right_length = len(left), len(right)
    while left_index != left_length and right_index != right_length:
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        elif left[left_index] > right[right_index]:
            merged.append(right[right_index])
            right_index += 1
        else:
            merged.append(left[left_index])
            merged.append(right[right_index])
            left_index += 1
            right_index += 1
    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged


print(merge_sort([2, 3, 14, 12, 4, 5, 51, 35, 23, 63, 45, 34, 7, 8, 79, 89]))

퀵 정렬에서 봤던 의사(pseudo) 코드 스타일로 코딩했습니다.
간단해서 개념 이해하긴 좋은 듯합니다. 

리스트를 나누지 않고  위치만 재귀로 내려주면서, 즉 하나의 리스트를 유지하면서 정렬하는 방식이 흔합니다.  
하지만, 퀵 정렬 때 테스트해보니 파이썬에서는 속도가 빠르지 않더군요. 이번에도 그럴 것 같아서.. 패스.... 

어차피 내장 정렬 쓰실 거잖아요... ~!

이 분이 폰 노이만