[알고리즘] 병합 정렬(Merge Sort)

병합 정렬(Merge Sort)란?

• 분할 정복 알고리즘중 하나
• 재귀용법을 활용한 정렬 알고리즘
1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다

분할 정복이란?

• 분할 정복
• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀어 다시 합병하여 문제의 답을 얻는 알고리즘
• 하양식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
• 문제를 잘게 쪼갤 때 부분 문제는 서로 중복되지 않는다.

 

병합 정렬(Merge Sort) 이해

• 하나의 리스트를 두개의 리스트로 분할하고 분할된 리스트를 정렬한다음 두 개의 정렬된 리스트를 합하여 정렬된 전체 리스트로 만드는 방법
• 병합 정렬의 단계
1. 분할(Divide): 입력 배열을 같은크기의 2개의 부분 배열로 분할한다.
2. 정복(Conquer): 부분 배열을 정렬한다.
3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

병합 정렬(Merge Sort) 구현

def merge_split(data):
    divide = len(data)/2 # 리스트를 반으로 나누기 위한 변수
    left = merge_split(data[:divide]) # 재귀함수를 이용하여 분할이 안될 때 까지 분할
    right = merge_split(data[divide:])
    return merge(left, right)
    
def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
    
    # left / right가 아직 남아있을 때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1
    
    # left만 남아있을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
        
    return merged

 

병합 정렬(Merge Sort) 시간 복잡도

• 단계의 깊이를 depth라고 하고 i로 놓고, 가장 윗 단계는 0으로 정한다.
• 다음 그림은 n/2^2는 2단계 깊이라고 정해놓는다.
• 각 단계에는 2^i개의 노드가 있다.
• 따라서, 각 단계는 항상 2^i * n/2^i = O(n)
• 단계는 항상 logn개 만큼 만들어진다.
• 따라서 시간 복잡도는 O(n) * O(logn) = O(nlogn)이 된다.