[알고리즘] 파이썬으로 병합 정렬 구현하기 :: merge sort in python :: bottom up 방식

파이썬으로 bottom-up 방식 merge sort 구현하기

1. merge sort란?

합병정렬/병합정렬은 반씩 분할해서 다시 합치면서 정렬하는 방식이다.

https://ko.wikipedia.org/wiki/합병_정렬#/media/파일:Merge-sort-example-300px.gif

2. merge sort in python

이를 python3에서 구현하면 다음과 같다.

# merge sort
def merge(left, right) :
    v=list()
    i=0;j=0
    while(i<len(left) and j<len(right)) :
        if left[i]<=right[j] :
            v.append(left[i])
            i+=1
        else :
            v.append(right[j])
            j+=1
    if i==len(left) : v = v + right[j:len(right)]
    if j == len(right): v = v + left[i:len(left)]
    return v
 
def merge_sort(v) :
    if len(v) <= 1 : return v
    m = len(v)//2
    left = merge_sort(v[0:m])
    right = merge_sort(v[m:len(v)])
    return merge(left, right)

merge_sort() 에서 list를 반으로 계속 분할하고, merge() 에서 분할된 두 list를 순서대로 정렬하면서 합친다.

* merge() 예시

> left = [1, 2, 5, 7, 8]

> right = [0, 3, 4, 6, 9]

> merge(left, right)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

ㅁ : left/ ㅁ : right

left list에 1과 right list에 0 중 0이 더 작기 때문에 0을 return할 list에 집어넣고, right list의 j 인덱스는 하나 더해준다.

위와 같은 방법으로 1과 3 중에는 1이 더 작기 때문에 1을 return할 list에 넣고, i 인덱스는 하나 더해준다.

이를 right와 left list 중 하나가 다할 때 까지 반복한다.

이후 return할 list와 남은 list 요소들을 합해준다.

* merge_sort() 예시

> merge_sort([0, 5, 7, 6, 1, 2, 8, 3, 4, 9])

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

input으로 들어간 10개의 요소로 이루어진 list는 5:5로 분해된다.

5:5로 분해된 요소는 다시 반으로 분해된다.

결국 하나의 요소만 남았을 때 return하고, return된 left 요소와 right요소들은 merge(left, right)에서 정렬되면서 합쳐진다.