병합 정렬(Merge Sort)

병합 정렬(Merge Sort)

분할 정복 알고리즘

; 작게 나눠 정렬된 상태로 만든 뒤, 그 정렬된 결과들을 합치면서 전체 정렬을 완성하는 알고리즘

리스트를 절반씩 나누고, 각각 정렬한 뒤 병합(merge) 단계에서 두 정렬된 리스트를 하나로 합침

----🐢

동작 방식

분할(Divide)

리스트(또는 배열)를 반으로 나눔

정복(Conquer) / 재귀적 정렬

나눠진 리스트가 길이 1 이하가 될 때까지 계속 분할

길이가 1인 리스트는 이미 정렬된 상태로 볼 수 있음

병합(Merge)

분할된 리스트를 정렬된 상태로 합치며 올라옴

두 개의 정렬된 리스트(서브리스트)를 하나의 큰 정렬된 리스트로 병합

---🐢-

동작 과정 예시

[12, 11, 13, 5, 6, 7] 병합 정렬

분할

[12, 11, 13, 5, 6, 7]를 두 부분으로 나누기

 왼쪽: [12, 11, 13]

 오른쪽: [5, 6, 7]

각각을 다시 두 부분으로 나누기 (재귀)

 왼쪽 [12, 11, 13]

  [12] / [11, 13]

  [11, 13] → [11] / [13]

 오른쪽 [5, 6, 7]

  [5] / [6, 7]

  [6, 7] → [6] / [7]

이 과정을 반복해 모두 길이 1 이하 리스트가 됨

병합

이제 분할이 끝났으니 길이 1인 리스트들을 정렬된 상태로 합침

예: [11] 과 [13] → [11, 13]

[12] 와 [11, 13] → 이 두 리스트를 정렬된 순서로 합치면 [11, 12, 13]

오른쪽도 동일: [6] 과 [7] → [6, 7], 그 뒤 [5] 와 [6, 7] → [5, 6, 7]

마지막으로 [11, 12, 13] 과 [5, 6, 7] 를 병합 → [5, 6, 7, 11, 12, 13]

 

# 병합 과정에서 두 개의 정렬된 서브리스트를 하나로 합칠 때는, 각 서브리스트에 대해 포인터를 두고, 두 리스트의 현재 요소를 비교하여 더 작은 것을 결과 리스트에 삽입한 뒤 포인터를 이동하는 방식을 사용

--🐢--

코드 예시

def merge_sort(arr):
    # 리스트 길이가 1 이하이면 이미 정렬된 상태
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        # 분할 -> 재귀로 각각 정렬
        merge_sort(left_half)
        merge_sort(right_half)

        # 병합(Merge) 단계
        i = j = k = 0
        
        # 두 리스트의 각 요소를 비교하며 병합
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 남은 요소들 처리
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

if __name__ == "__main__":
    data = [12, 11, 13, 5, 6, 7]
    merge_sort(data)
    print("정렬 결과:", data)
    # 정렬 결과: [5, 6, 7, 11, 12, 13]

길이 1 이하일 때까지 분할 (재귀)

분할된 부분 리스트들이 정렬된 상태로 돌아온 뒤, merge 단계에서 정렬된 하나의 리스트로 합침

병합 시 두 포인터(i, j)를 사용해, 더 작은 원소를 메인 배열(arr[k])에 복사하고 포인터 이동

-🐢---

시간 복잡도

분할: 매번 리스트를 절반으로 나누므로 log n번 분할

병합: 각 단계에서 리스트 전체 원소를 한 번씩 확인하므로 O(n)

결합: O(n) * O(log⁡ n) = O(n log⁡ n)

최악/평균/최선: 모두 O(n log⁡ n)

; 이는 어떤 형태의 입력이 와도 분할과 병합이 동일하게 수행되기 때문

🐢----

장단점

장점

최악/평균/최선 모든 경우에 O(n log n)

안정 정렬: 중복 원소가 있을 때, 입력에서의 순서가 출력 순서로 유지

리스트가 큰 경우나 분산된 메모리에 있을 경우, 분할 정복 특성상 성능이 좋을 수 있음

단점

추가 메모리(공간 복잡도 O(n))가 필요

작은 배열을 쪼개도 병합 절차가 발생

→ 상수 계수(overhead)가 크며, 실제로는 퀵 정렬보다 다소 느릴 수 있음

인플레이스 구현(추가 공간 없이)은 일반적으로 어렵고 복잡