병합 정렬(Merge Sort): 안정적인 분할 정복 기반 정렬 알고리즘

🔹 병합 정렬이란?

1. 병합 정렬(Merge Sort)의 정의

병합 정렬(Merge Sort)은 분할 정복(Divide & Conquer) 방식을 사용하여 배열을 분할하고, 정렬된 하위 배열을 병합하여 정렬하는 효율적인 알고리즘입니다.

✅ 병합 정렬의 주요 특징:

• 배열을 반으로 나눈 후 재귀적으로 정렬
• 최악의 경우에도 O(n log n)의 시간 복잡도를 보장
• 안정 정렬(Stable Sort), 즉 동일한 값의 상대적인 순서를 유지
• 추가적인 메모리 공간(O(n))이 필요

📌 병합 정렬은 안정적인 성능을 보장하며, 대규모 데이터 정렬에 적합합니다.

---

🔹 병합 정렬의 동작 과정

1. 배열을 절반으로 나눔 (Divide)
2. 각 부분 배열을 재귀적으로 정렬
3. 정렬된 하위 배열을 병합 (Merge)

✔️ 병합 정렬 예제 (Python):

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    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 = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(arr))

📌 병합 정렬은 재귀를 이용해 구현할 수 있으며, 정렬된 하위 배열을 효율적으로 병합합니다.

---

🔹 병합 정렬의 시간 복잡도 분석

케이스	시간 복잡도
최악의 경우 (O(n log n))	모든 경우에서 일정한 성능 보장
평균적인 경우 (O(n log n))	일반적인 무작위 데이터 정렬
최선의 경우 (O(n log n))	이미 정렬된 경우에도 O(n log n)

📌 퀵 정렬과 달리 최악의 경우에도 O(n log n)을 유지하므로 안정적인 성능을 보장합니다.

---

🔹 병합 정렬의 시각적 표현

✔️ 입력 배열: [5, 3, 8, 4, 2]

1. 배열 분할: [5, 3, 8] | [4, 2]
2. 추가 분할: [5] [3, 8] | [4] [2]
3. 정렬 및 병합: [3, 5, 8] | [2, 4]
4. 최종 병합: [2, 3, 4, 5, 8]

📌 병합 정렬은 정렬된 작은 리스트를 병합하여 전체 정렬을 완성합니다.

---

🔹 병합 정렬의 장점과 단점

✅ 장점:

• O(n log n)의 일정한 시간 복잡도를 유지
• 안정 정렬(Stable Sort)로 동일한 값의 순서가 유지됨
• 연속된 메모리 할당이 필요하지 않아 외부 정렬(External Sorting)에 유리

❌ 단점:

• 추가적인 메모리(O(n))가 필요하여 공간 효율성이 낮음
• 짧은 리스트에서는 퀵 정렬보다 성능이 떨어질 수 있음
• 연결 리스트에서는 효과적이지만, 배열에서는 메모리 비용이 높음

📌 메모리 사용량이 많지만, 일관된 성능을 보장하는 것이 강점입니다.

---

🔹 병합 정렬 vs 다른 정렬 알고리즘 비교

정렬 알고리즘	최악 시간 복잡도	평균 시간 복잡도	공간 복잡도	안정 정렬
버블 정렬	O(n²)	O(n²)	O(1)	O
선택 정렬	O(n²)	O(n²)	O(1)	X
삽입 정렬	O(n²)	O(n²)	O(1)	O
병합 정렬	O(n log n)	O(n log n)	O(n)	O
퀵 정렬	O(n²)	O(n log n)	O(log n)	X

📌 병합 정렬은 안정적인 O(n log n) 성능을 보장하지만, 추가 메모리 사용이 필요합니다.

---

📌 결론

✅ 병합 정렬(Merge Sort)은 분할 정복 방식을 사용하여 데이터를 안정적으로 정렬하는 알고리즘입니다.
✅ O(n log n)의 일정한 성능을 보장하며, 대량의 데이터에서도 효율적입니다.
✅ 추가적인 메모리를 사용해야 하지만, 안정 정렬이 필요한 경우 적합합니다.
✅ 퀵 정렬과 비교했을 때 최악의 경우에도 안정적인 성능을 유지하는 장점이 있습니다.