병합정렬(Merge Sort) 파헤치기

✅ 병합 정렬 (Merge Sort)란?

"분할 정복(Divide and Conquer)" 전략을 사용하는 정렬 알고리즘입니다.

• 배열을 반으로 쪼개고
• 각 부분을 재귀적으로 정렬한 뒤
• 두 정렬된 부분을 하나로 합쳐서(merge) 최종 정렬된 배열을 만듭니다.
• 병합 정렬은 배열을 왼쪽 → 오른쪽 순서대로 나누고 병합합니다.

---

🔄 병합 정렬 동작 순서

예: [5, 2, 4, 1, 3]

분할 단계 (Divide)

[5,2,4,1,3]
→ [5,2] [4,1,3]
→ [5][2] [4][1,3]
→ [1][3]

최종 분할 결과

[5] [2] [4] [1] [3]

 

병합 단계 (Merge)

→ [2,5]
→ [1,3] → [1,3,4]
→ [1,2,3,4,5]

 

병합 순서 : 가장 마지막에 나뉜 조각들부터 병합하기 시작해요 (재귀 구조의 특성).

병합 대상 순서:

1. [5] + [2] → [2, 5]
2. [1] + [3] → [1, 3] 
3. [4] + [1, 3] → [1, 3, 4]
4. [2, 5] + [1, 3, 4] → [1, 2, 3, 4, 5]

---

 

배열을 근데 왜 저런 형식으로 나누는가..? 절반을 나누는데 한쪽은 홀수가 되고 한쪽은 짝수가 된다? 이러한 궁금증이 발생하였습니다. 

✅ 핵심 규칙: 홀수 개의 배열 분할

배열 길이가 홀수라면 → 왼쪽 절반은 ⌊n/2⌋개, 오른쪽은 (n - ⌊n/2⌋)개

• ⌊n/2⌋ = n을 2로 나눈 내림값 (Java에서 그냥 n / 2)
• 오른쪽은 나머지 수를 모두 가짐

---

📌 예시: 배열 길이 = 5

배열: [5, 2, 4, 1, 3] (길이 5)

int mid = arr.length / 2;  // 5 / 2 = 2

→ mid = 2 → 두 배열로 나누면:

• 왼쪽: [5, 2] (index 0,1)
• 오른쪽: [4, 1, 3] (index 2,3,4)

⚠️ 자바에서 Arrays.copyOfRange(arr, 0, mid) 는 0~(mid-1)까지 복사
즉, 0~1 복사 → [5, 2]
mid~arr.length 복사 → 2~4 복사 → [4, 1, 3]

---

🔄 병합 정렬은 항상 이렇게 나눈다

배열 길이	나눔 결과
5	왼쪽: 2개, 오른쪽: 3개
7	왼쪽: 3개, 오른쪽: 4개
9	왼쪽: 4개, 오른쪽: 5개

 

→ 즉, 병합 정렬은 항상 왼쪽이 조금 작고, 오른쪽이 1개 더 많을 수 있어요.

---

⏱ 시간 복잡도 분석

경우	복잡도	설명
최선	O(n log n)	항상 log₂n 단계의 분할 + n번의 병합 필요
평균	O(n log n)	분할/병합 구조는 항상 동일
최악	O(n log n)	분할/병합 횟수는 데이터 정렬 상태에 영향받지 않음

 

병합 정렬은 데이터가 이미 정렬된 상태여도, 병합 과정은 그대로 수행됨 → 항상 O(n log n)

---

🧠 병합 정렬의 핵심 특성

특성	설명
안정 정렬	같은 값의 순서가 유지됨 (예: 5a, 5b → 정렬 후에도 a가 앞)
재귀 사용	구현 시 재귀함수를 사용해 분할 진행
추가 메모리 필요	병합 단계에서 새로운 배열에 복사 필요 → 공간복잡도 O(n)
정렬 상태 무관	입력 데이터의 정렬 여부와 관계없이 항상 O(n log n) 보장

---

📌 자바 코드 예시 (직접 구현)

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr.length <= 1) return;

        int mid = arr.length / 2;

        // 분할
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        mergeSort(left);
        mergeSort(right);

        // 병합
        merge(arr, left, right);
    }

    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        // 두 배열을 비교하며 작은 값을 arr에 저장
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) arr[k++] = left[i++];
            else arr[k++] = right[j++];
        }
        // 남은 요소 복사
        while (i < left.length) arr[k++] = left[i++];
        while (j < right.length) arr[k++] = right[j++];
    }
}

---

✅ 병합 정렬 요약

항목	병합정렬
시간 복잡도	O(n log n) (항상 일정)
공간 복잡도	O(n) (추가 배열 필요)
정렬 안정성	✅ 안정 정렬
실전 활용도	매우 높음 (자바, 파이썬 내부 정렬에 기반 포함됨)

---

🆚 버블 정렬과 비교

항목	버블 정렬	병합 정렬
시간복잡도(최악)	O(n²)	O(n log n)
최적화 가능	최선 O(n) (스왑 여부 확인 시)	항상 O(n log n)
공간 사용	O(1)	O(n)
실무 사용	거의 없음	✅ 적극 사용됨