병합 정렬 (Merge Sort)

병합 정렬

"분할 정복(Divide and Conquer) 방식으로 동작하는 정렬 알고리즘"

• 배열을 반으로 나눈 후 각각 정렬하고, 다시 합치는 과정
• 퀵 정렬처럼 O(n log n) 시간복잡도를 가지며, 안정적인 정렬 방식
• 추가적인 메모리 공간(O(n))을 사용해야 하는 단점이 있음

---

병합 정렬 동작 원리

3가지 과정 (Divide → Conquer → Merge)

1. 분할(Divide)
   • 리스트를 반씩 나누어 최소한의 단위(한 개의 요소)가 될 때까지 재귀적으로 나눔
2. 정복(Conquer)
   • 분할된 리스트를 개별적으로 정렬
3. 병합(Merge)
   • 정렬된 두 개의 리스트를 하나의 정렬된 리스트로 병합
    

# Pseudo Code
FUNCTION MergeSort(arr)
    IF length(arr) <= 1 THEN
        RETURN arr  # 리스트 크기가 1 이하이면 이미 정렬됨

    SET mid TO length(arr) / 2
    SET left TO MergeSort(arr[0 : mid])  # 왼쪽 반 나누기
    SET right TO MergeSort(arr[mid : end])  # 오른쪽 반 나누기

    RETURN Merge(left, right)  # 정렬된 두 리스트 병합
END FUNCTION

FUNCTION Merge(left, right)
    SET result TO empty list
    WHILE left is not empty AND right is not empty DO
        IF left[0] <= right[0] THEN
            APPEND left[0] TO result
            REMOVE left[0] FROM left
        ELSE
            APPEND right[0] TO result
            REMOVE right[0] FROM right
    END WHILE

    APPEND remaining elements of left TO result
    APPEND remaining elements of right TO result

    RETURN result
END FUNCTION


# Full Code
def merge_sort(arr):
    if len(arr) <= 1:
        return arr  # 리스트 크기가 1 이하이면 정렬 완료

    mid = len(arr) // 2  # 리스트를 반으로 나눔
    left = merge_sort(arr[:mid])  # 왼쪽 리스트 정렬
    right = merge_sort(arr[mid:])  # 오른쪽 리스트 정렬

    return merge(left, right)  # 정렬된 리스트 병합

def merge(left, right):
    result = []
    i = 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

    # 남은 요소 추가
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result


# 테스트
arr = [44, 75, 23, 43, 55, 12, 64, 77, 33]
sorted_arr = merge_sort(arr)
print("병합 정렬 결과:", sorted_arr)

---

병합 정렬의 시간복잡도

경우	시간복잡도
최선 (이미 정렬됨)	O(n log n)
평균	O(n log n)
최악 (역순 정렬)	O(n log n)

 

✅ 항상 O(n log n)의 성능을 보장 (퀵 정렬보다 안정적)

❌ 추가 메모리(O(n)) 사용 → 공간복잡도는 퀵 정렬보다 불리함

---

병합 정렬의 장단점

장점

 

• 항상 O(n log n)의 성능을 보장 → 퀵 정렬보다 안정적
• Stable Sort (안정 정렬) → 동일한 값의 순서가 유지됨
• Linked List 정렬에 적합 → 추가 메모리 공간을 활용할 수 있음

단점

• 추가적인 메모리 공간(O(n)) 필요 → 메모리 사용량 증가
• 배열을 병합하는 과정에서 오버헤드 발생 → 퀵 정렬보다 느릴 수 있음

결론

병합 정렬은 퀵 정렬보다 안정적이지만 추가 메모리를 사용해야 한다는 단점입니다. 대규모 데이터 정렬보다는 데이터가 안정적으로 정렬되어야 하는 경우에 적합합니다.