C# - 병합 정렬 (Merge Sort)

🧩 병합 정렬 (Merge Sort) – 항상 안정적인 분할 정복 정렬

1. 개념

병합 정렬은 분할 정복(Divide and Conquer) 알고리즘의 대표 예시이다.
배열을 반으로 나누고, 나눈 배열을 각각 정렬한 후, 두 정렬된 배열을 **병합(merge)**하여 최종 정렬된 배열을 만든다.

---

2. 작동 방식 요약

1. 배열을 반으로 분할
2. 각각을 재귀적으로 병합 정렬
3. 두 정렬된 배열을 정렬된 상태로 병합
4. 더 이상 나눌 수 없을 때까지 반복

---

3. C# 예제 코드 (새로운 예시)

void MergeSort(int[] arr, int left, int right)
{
    if (left >= right) return;

    int mid = (left + right) / 2;

    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);
    Merge(arr, left, mid, right);
}

void Merge(int[] arr, int left, int mid, int right)
{
    int[] temp = new int[right - left + 1];

    int i = left;
    int j = mid + 1;
    int k = 0;

    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }

    while (i <= mid)
        temp[k++] = arr[i++];
    while (j <= right)
        temp[k++] = arr[j++];

    // 원래 배열에 복사
    for (int t = 0; t < temp.Length; t++)
        arr[left + t] = temp[t];
}

✅ 사용 예:

int[] data = { 6, 2, 9, 1, 5 };
MergeSort(data, 0, data.Length - 1);

---

4. 시간/공간 복잡도

경우	시간 복잡도
평균	O(n log n)
최악	O(n log n)

 

• 공간 복잡도: O(n)
  → 정렬을 위해 임시 배열이 필요함

---

5. 특징

• 항상 안정적인 시간 복잡도 O(n log n)
• 안정 정렬 (동일 값의 순서 보존)
• 추가 메모리 공간 필요 (In-place 아님)
• 큰 데이터, 안정성이 중요한 경우에 적합

---

6. 예시

[4, 1, 3, 2]
→ 나누기: [4, 1] / [3, 2]
→ 정렬: [1, 4] / [2, 3]
→ 병합: [1, 2, 3, 4]

---

7. 마무리 요약

• 병합 정렬은 시간 복잡도가 항상 O(n log n)으로 예측 가능하여 신뢰도가 높다.
• 퀵 정렬보다 느릴 수 있지만, 데이터가 정렬된 상태와 무관하게 안정적인 성능을 낸다는 점에서 강력한 선택이다.
• 추가 메모리가 필요하다는 점은 고려해야 한다.