[합병 정렬] Merge sort - python

출처:https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

Merge Sort

---

시간복잡도:

합병 정렬(병합 정렬)(merge sort)은 비교 기반 정렬 알고리즘이다.

일반적인 방법으로 구현했을 때, 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘(divide and qonquer algorithm)의 하나이다.

존 폰 노이만이 1945년에 개발했다.

(분할 정복 알고리즘: 보통 재귀 함수(recursive function)를 통해 구현된다.

def F(x):

if F(x)의 문제(종료 조건을 걸어주자):

return f(x)직접 계산

else:

x를 a1, a2로 부할

F(a1)과 F(a2) 호출

return F(a1), F(a2)로 부터 F(x)를 구한값

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a)//2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left,right)
 
def merge(left, right):
    result = []
    while len(left) > 0 or len(right)>0:
        if len(left) > 0 and len(right) > 0:
 
            if left[0] <= right[0]:
                result.append(left[0])
                left=left[1:]
            else:
                result.append(right[0])
                right = right[1:]
 
        elif len(left) > 0:
            result.append(left[0])
            left = left[1:]
        elif len(right) > 0:
            result.append(right[0])
            right = right[1:]
    return result
 
 
a = [6, 5, 3, 1, 8, 7, 2, 4]
 
print(merge_sort(a))

사진의 예 6, 5, 3, 1, 8, 7, 2, 4를 넣어본 결과는 아래와 같당. 

left: [6] / right: [5]

merge: [5, 6]

left: [3] / right: [1]

merge: [1, 3]

left: [5, 6] / right: [1, 3]

merge: [1, 3, 5, 6]

left: [8] / right: [7]

merge: [7, 8]

left: [2] / right: [4]

merge: [2, 4]

left: [7, 8] / right: [2, 4]

merge: [2, 4, 7, 8]

left: [1, 3, 5, 6] / right: [2, 4, 7, 8]

merge: [1, 2, 3, 4, 5, 6, 7, 8]

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