병합 정렬

Merge Sort

💡 병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 전략을 사용하는 효율적인 정렬 알고리즘 중 하나

 

작동 원리

http://algorithm.wiki/ko/app/

 

1. 분할(Divide): 주어진 배열을 절반으로 나눕니다. 이 분할 과정은 원소가 하나만 남을 때까지 재귀적으로 계속됩니다.
2. 정복(Conquer): 분할된 작은 문제들을 해결합니다. 병합 정렬에서 이 단계는 원소가 하나만 있는 배열이므로 이미 정렬된 상태입니다.
3. 병합(Merge): 정렬된 두 개의 부분 배열을 하나의 정렬된 배열로 병합합니다. 이 과정은 재귀적으로 수행되며, 전체 배열이 정렬될 때까지 계속됩니다.

시간 복잡도

• 최선, 평균, 최악의 경우 모두: O(nlogn)

공간 복잡도

• O(n) (추가적인 메모리 공간이 필요합니다.)

장단점

• 장점
  • 데이터의 크기에 상관없이 항상 O(nlogn)의 시간 복잡도를 갖습니다.
  • 안정적인 정렬(stable sort)입니다.
• 단점
  • 원래 배열 외에 추가적인 메모리 공간이 필요하므로, 메모리 사용이 효율적이지 않을 수 있습니다.

구현

def merge(left, right):
    result = []
    left_idx, right_idx = 0, 0

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

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

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

    return result

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)