[Algorithm] 병합 정렬 (Merge Sort)

 

 

 

 

병합 정렬 (Merge Sort)

병합 정렬은 재귀를 이용하는 분할 정복 알고리즘.

 

분할  →   배열을 쪼개는 것.

정복  →   분할한 배열을 정렬하면서 하나로 합병하는 것.

 

 

 

작동 방식

• 정렬하려는 배열을 크기가 0 또는 1이 될 때까지 절반씩 분할.
• 분할된 배열은 다시 하나의 배열로 합쳐지면서 정렬.

예시

• 배열 [8, 3, 2, 1, 7, 6, 4, 5]가 있을 때 다음과 같은 과정으로 정렬한다. (오름차순)
• 분할
  1. 8 3 2 1 7 6 4 5
  2. 8 3 2 1  |  7 6 4 5
  3. 8 3  |  2 1  |  7 6  |  4 5
  4. 8  |  3  |  2  |  1  |  7  |  6  |  4  |  5
• 정렬
  1. 6 7  |  4 5  |  _ _ _ _
  2. 6 7  |  _ 5  |  4 _ _ _
  3. 6 7  |  _ _  |  4 5 _ _
  4. _ 7  |  _ _  |  4 5 6 _
• 합병
  1. 8  |  3  |  2  |  1  |  7  |  6  |  4  |  5
  2. 3 8  |  1 2  |  6 7  |  4 5
  3. 1 2 3 8  |  4 5 6 7
  4. 1 2 3 4 5 6 7 8

시간 복잡도

• 합병 정렬     : O(nlogn)
• 정렬             : O(n)
• 분할 or 합병 : O(logn)

 

 

 

def merge_sort(arr):
    if len(arr) < 2:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid+1:])
    
    merged_arr = []
    l = r = 0
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            merged_arr.append(left[l])
            l += 1
        else:
            merged_arr.append(right[r])
            r += 1
    
    merged_arr += left[l:]
    merged_arr += right[r:]
    return merged_arr