파이썬으로 구현하는 병합정렬(Merge Sort)

Concept

병합정렬은 분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘으로, 시간복잡도는 O(nlogn)이다

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 정렬방법이다.  이때 병합 정렬은 아래와 같은 분할 정복 메커니즘을 따르게 된다

 

병합정렬; 오름차순

- 분할(Divide): 입력 리스트를 같은 크기의 2개의 부분 리스트로 분할한다

- 정복(Conquer): 부분 리스트를 정렬한다

- 결합(Combine): 정렬된 부분 리스트를 하나의 리스트에 통합한다

   *이 때 그림에서 표현은 생략되었으나 부분 리스트의 크기가 1이 될 때까지 분할 후 정렬 후 합병과정을 거치게 된다

 

 

구현 코드

1) 정렬되지 않은 데이터 -> 리스트로 입력 받기

>>>27 10 12 20 25 13
unsorted_list = [int(x) for x in input().split()]

 

2) 쪼개진 부분 리스트의 길이가 1이 될때까지 분할

def merge_sort(unsorted_list):
    # 크기가 1이하면 반환
    if len(unsorted_list) <= 1:
    	return unsorted_list
     
    # 리스트를 2분할
    mid = len(unsorted_list)//2
    left = unsorted_list[:mid]
    right = unsorted_list[mid:]
    
    # 2분할한 리스트를 각각 merge sort진행
    left_ = merge_sort(left)
    right_ = merge_sort(right)
    return merge(left_, right_)

 

3) 길이가 1로 쪼개진 리스트를 순서대로 병합하여 정렬 리스트에 저장

def merge(left, right):
    i, j = 0,0
    sorted_list = []
    
    while i < len(left) and j < len(right):
    	if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1
    while i < len(left):
    	sorted_list.append(left[i])
        i += 1
    while j < len(right):
    	sorted_list.append(right[j])
        j += 1
    return sorted_list

4) 정렬결과 확인

print(merge_sort(unsorted_list))
>>>10 12 13 20 25 27