병합 정렬(Merge Sort)

병합 정렬(Merge Sort)

개념

• 분할 정복 알고리즘 
• 주어진 배열을 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후 다시 크기 순으로 재배열
• 안정 정렬 

코드

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

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    result = []
    i = 0
    j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    while i < len(left):
        result.append(left[i])
        i += 1

    while j < len(right):
        result.append(right[j])
        j += 1

    return result

 

특징

• 장점
  • 데이터의 분포에 영향을 덜 받는다.
• 단점 
  • 임시 배열이 필요하다.

시간 복잡도

• 분할 단계
  • 비교 연산과 이동 연산이 수행되지 않는다.
• 합병 단계
  • 순환 호출의 깊이 만큼의 합병 단계(log2N) * 각 합병 단계의 비교 연산(N) = Nlog2N

 

참고

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog