병합 정렬(Merge Sort)

🔷 병합 정렬(Merge Sort)란?

병합 정렬은 분할 정복(Divide and Conquer) 알고리즘을 기반으로 하는 정렬 방식으로, 데이터를 작게 나누고 다시 정렬하며 합치는 방식으로 동작합니다. 데이터의 크기와 무관하게 항상 안정적이고 예측 가능한 성능을 보장하기 때문에 많은 환경에서 사용됩니다.

 

병합정렬

---

✅ 작동 원리 (어떻게 작동하나요?)

1. 배열을 반으로 나눕니다.
2. 나눈 배열 각각을 다시 반으로 나눕니다.
3. 배열이 더 이상 쪼갤 수 없을 때까지(길이 1일 때까지) 반복합니다.
4. 이후 작은 배열들을 정렬된 상태로 병합합니다.
5. 모든 배열이 병합되면 최종적으로 정렬된 하나의 배열이 됩니다.

👉 쉽게 말해, 쪼개고, 쪼개고, 나중에 정렬하면서 합치는 것!

---

✅ 시간 및 공간 복잡도

구분복잡도

최선	O(n log n)
평균	O(n log n)
최악	O(n log n)
공간 복잡도	O(n) (새로운 배열이 필요함)

 

---

🔷 장점과 단점

✅ 장점

• 항상 안정적인 성능을 보임 (O(n log n))
• 안정 정렬: 동일한 값의 원소 순서가 유지됨
• 큰 데이터를 정렬할 때 매우 유리함

❌ 단점

• 추가 메모리 공간 필요 (비교적 공간 효율이 낮음)
• 구현이 상대적으로 복잡함

---

🔷 Java 예제 코드

public class MergeSortExample {

    // 병합 정렬 메서드
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // 배열을 절반으로 나누기
            int mid = (left + right) / 2;

            // 왼쪽 절반 정렬
            mergeSort(arr, left, mid);

            // 오른쪽 절반 정렬
            mergeSort(arr, mid + 1, right);

            // 정렬된 두 배열 병합
            merge(arr, left, mid, right);
        }
    }

    // 병합(Merge) 메서드
    public static void merge(int[] arr, int left, int mid, int right) {
        // 배열의 크기 계산
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 임시 배열 생성
        int[] L = new int[n1];
        int[] R = new int[n2];

        // 데이터 복사
        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[mid + 1 + j];

        // 병합
        int i = 0, j = 0;
        int k = left;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // 남은 요소 복사
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // 배열 출력 메서드
    public static void printArray(int[] arr) {
        for (int num : arr)
            System.out.print(num + " ");
        System.out.println();
    }

    // 실행 메서드
    public static void main(String[] args) {
        int[] numbers = {38, 27, 43, 3, 9, 82, 10};

        System.out.println("정렬 전 배열:");
        printArray(numbers);

        mergeSort(numbers, 0, numbers.length - 1);

        System.out.println("정렬 후 배열:");
        printArray(numbers);
    }
}

✅ 출력 결과

정렬 전 배열:
38 27 43 3 9 82 10
정렬 후 배열:
3 9 10 27 38 43 82

---

 

🔷 정리하면?

항목내용

정렬 방식	분할 후 병합 (Divide and Conquer)
정렬 속도	항상 O(n log n)
공간 사용	O(n) (추가 배열 필요)
안정성	안정 정렬 (순서 유지)
활용 예	대량 데이터 정렬, 외부 정렬 등

 

---