[Python] 병합정렬

병합정렬

데이터의 요소들을 두 그룹으로 나눈 후 정렬하고, 정렬된 두 그룹을 비교하며 하나로 합치는 알고리즘이다.

 

병합정렬과정

#숫자 8개를 반으로 나눈다 
group1 = [2, 8, 4, 7]
group2 = [6, 1, 3, 5]

#두 그룹을 정렬한다.
group1 = [2, 4, 7, 8]
group2 = [1, 3, 5, 6]

#두 그룹을 하나의 그룹으로 합친다.
두 그룹의 첫번째 값을 비교해 작은 값을 새로운 리스트(result)에 넣는다.
group1 = [2, 4, 7, 8]
group2 = [3, 5, 6]
result = [1]

#두 그룹의 첫번째 값을 비교해 작은 값을 새로운 리스트에 넣는 것을 반복한다.
group1 = [4, 7, 8]
group2 = [3, 5, 6]
result = [1, 2]

group1 = [4, 7, 8]
group2 = [5, 6]
result = [1, 2, 3]

group1 = [7, 8]
group2 = [5, 6]
result = [1, 2, 3, 4]

group1 = [7, 8]
group2 = [6]
result = [1, 2, 3, 4, 5]

group1 = [7, 8]
group2 = []
result = [1, 2, 3, 4, 5, 6]

#group2에는 자료가 없으므로 group1에 남아있는 자료를 모두 result로 옮긴다.
group1 = []
group2 = []
result = [1, 2, 3, 4, 5, 6, 7, 8]

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

병합정렬 알고리즘

def merge_sort(a):
    n = len(a)

    if n <= 1:
        return

    mid = n // 2
    g1 = a[:mid]
    g2 = a[mid:]
    merge_sort(g1)
    merge_sort(g2)

    i = 0
    j = 0
    k = 0

    while i < len(g1) and j < len(g2):
        if g1[i] < g2[j]:
            a[k] = g1[i]
            i += 1
            k += 1
        else:
            a[k] = g2[j]
            j += 1
            k += 1
    
    while i < len(g1):
        a[k] = g1[i]
        i += 1
        k += 1
    while j < len(g2):
        a[k] = g2[j]
        j += 1
        k += 1

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
merge_sort(d)
print(d)

또 다른 방법

def merge_sort(a):
    n = len(a)

    if n <= 1:
        return a
    
    mid = n // 2
    g1 = merge_sort(a[:mid])
    g2 = merge_sort(a[mid:])
    result = []
    while g1 and g2:
        if g1[0] < g2[0]:
            result.append(g1.pop(0))
        else:
            result.append(g2.pop(0))
    while g1:
        result.append(g1.pop(0))
    while g2:
        result.append(g2.pop(0))
    return result

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(merge_sort(d))

참고

병합정렬의 시간복잡도는 O(N * logN)이다.