[python] 알고리즘 - 병합 정렬(Merge Sort)

병합 정렬(Merge Sort)

출처: https://visualgo.net/en

 

병합 정렬은 배열을 좌, 우로 나누고, 나눈 배열을 정렬하고 다시 붙인다. 이 과정을 반복한다. 퀵 소트와 마찬가지로 재귀 용법을 활용하는 알고리즘이다. 

 

 

출처: https://en.wikipedia.org/wiki/Merge_sort

위키피디아에서 제공하는 이미지가 더 도움이되는 것 같다. 아래 코드 과정을 일일히 손으로 써보면 위와 같은 구조로 진행됨을 확인할 수 있다. (*재귀를 정확히 이해해야 코드를 이해할 수 있다.)

 

[python] 알고리즘 - 재귀 용법(Recursive Call)

 

#Merge Sort
def merge(array):
    if len(array) <= 1:
        return array
    
    mid = len(array) // 2
    left = merge(array[:mid])
    right = merge(array[mid:])
    
    return merge_func(left, right)

def merge_func(left, right):
    merge_list = []
    left_id, right_id = 0, 0
    
    #case1 left, right
    while len(left) > left_id and len(right) > right_id:
        if left[left_id] > right[right_id]:
            merge_list.append(right[right_id])
            right_id += 1
        else:
            merge_list.append(left[left_id])
            left_id += 1
    
    #case2 letf
    while len(left) > left_id and len(right) <= right_id:
        merge_list.append(left[left_id])
        left_id += 1
    
    #case3 right
    while len(right) > right_id and len(left) <= left_id:
        merge_list.append(right[right_id])
        right_id += 1
    
    return merge_list
    

#Test Code
import random
merge_array = random.sample(range(100), 10)

print(merge_array)
print(merge(merge_array))