병합정렬(MergeSort) 이론과 파이썬 구현

병합정렬(MergeSort)

 

병합정렬은 하나의 리스트를 같은 크기의 두개로 분할합니다.

분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합해 전체 정렬을 시킵니다.

각각의 부분 리스트를 정렬하기 위해 순환 호출하는 식으로 실행됩니다.

 

병합정렬은 분할 정복 방법에 바탕을 둡니다.

 

병합정렬에서 정렬이 이루어지는 시점은 두 개의 리스트를 병합하는 시점입니다. 

병합과정에서는 두 개의 리스트 요소들을 처음부터 비교해서 두 개의 리스트 요소 중 더 작은 요소를 리스트에 넣어줍니다.

두 리스트 중 하나가 끝날 때까지 이 과정을 반복합니다.

하나의 리스트가 먼저 끝나면 나머지 리스트의 요소들을 리스트에 넣어줍니다.

 

병합정렬을 이용한 병합과정

 

2 > 1 이기 때문에 1을 먼저 첫번째 위치에 넣어줍니다.

2 < 3 이기 때문에 2를 두번째 위치에 넣어줍니다.

4 > 3 이기 때문에 3을 세번째 위치에 넣어줍니다.

4 < 6 이기 때문에 4을 네번째 위치에 넣어줍니다.

5 < 6 이기 때문에 5를 다섯번째 위치에 넣어줍니다.

 

왼쪽 리스트가 끝났기 때문에 오른쪽 리스트의 나머지 요소들(6, 7)을 리스트에 넣어줍니다.

 

병합정렬을 이용한 전체 정렬 과정

 

병합정렬의 파이썬 코드입니다.

def merge_sort(a):
    if len(a) <= 1:
        return

    mid = len(a) // 2   
    one = a[:mid] 
    two = a[mid:]
   
    merge_sort(one)  # 왼쪽 정렬
    merge_sort(two)  # 오른쪽 정렬

    i = 0
    j = 0
    c = 0

    while i < len(one) and j < len(two):
        if one[i] < two[j]:
            a[c] = one[i]
            i += 1
        else:
            a[c] = two[j]
            j += 1
            
        c += 1 

    while i < len(one):
        a[c] = one[i]
        i += 1
        c += 1

    while j < len(two):
        a[c] = two[j]
        j += 1
        c += 1
     
b = [5, 2, 4, 6, 1, 7, 3]
merge_sort(b)

# 결과>>[1, 2, 3, 4, 5, 6, 7]
print(b)