[정렬] 병합 정렬

병합정렬

병합 정렬은 “분할 정복(Divide and Conquer)” 전략을 사용해 배열을 반으로 계속 나눈 뒤, 각각을 정렬하고 병합하면서 전체를 정렬하는 알고리즘이다.

복잡도

$O(nlogn)$

병합정렬은 일정한 성능을 보인다.

로직

1. 분할(Divide)
   • 배열을 절반( left~mid , mid+1~right )으로 나눈다.
   • 더 이상 나눌 수 없을 때까지 재귀 호출한다.
2. 정복(Conquer)
   • 나눠진 하위 배열을 정렬된 상태로 만든다.
   • 이 과정은 재귀적으로 해결된다.
3. 병합(Merge)
   • 두 개의 정렬된 배열을 하나로 병합한다.
   • temp 임시 배열을 활용해 안정적으로 합친다.

예시 코드

import java.util.Arrays;

/* 병합 정렬
 * - 분할 정복(Divide and Conquer) 기반 정렬 알고리즘
 * - 항상 O(n log n)의 성능을 보장
 * - 안정 정렬(Stable Sort)
 * - 추가 메모리 공간 O(n) 필요
 */
public class _ergeSort {

    /* n개의 정수를 병합 정렬로 오름차순 정렬 */
    public static void solution(int[] arr){
        System.out.println("원본 배열 : "  + Arrays.toString(arr));
        int[] temp = new int[arr.length]; // 임시 버퍼
        mergeSort(arr, temp, 0, arr.length - 1);
        System.out.println("정렬된 배열 : " + Arrays.toString(arr));
    }

    /* 분할 단계 (Divide) */
    private static void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left < right) { // 최소 두 개 이상의 요소가 있을 때만 분할
            int mid = (left + right) / 2;
            mergeSort(arr, temp, left, mid);      // 왼쪽 절반
            mergeSort(arr, temp, mid + 1, right); // 오른쪽 절반
            merge(arr, temp, left, mid, right);   // 병합 단계
        }
    }

    /* 병합 단계 (Merge) */
    private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        System.out.println("병합 전 : " + Arrays.toString(arr));
        System.out.println("left : " + left + ", mid : " + mid + ", right : " + right);

        // 병합 구간을 temp에 복사
        for (int i = left; i <= right; i++) {
            temp[i] = arr[i];
        }

        int leftIndex = left;
        int rightIndex = mid + 1;
        int current = left;

        // 두 구간을 비교하며 작은 값을 arr에 채워 넣기
        while (leftIndex <= mid && rightIndex <= right) {
            if (temp[leftIndex] <= temp[rightIndex]) {
                arr[current++] = temp[leftIndex++];   // 안정성 유지 (<=)
            } else {
                arr[current++] = temp[rightIndex++];
            }
        }

        // 왼쪽 배열에 남은 값 복사
        while (leftIndex <= mid) {
            arr[current++] = temp[leftIndex++];
        }

        System.out.println("병합 후 : " + Arrays.toString(arr));
        System.out.println("=====================");
    }
}

특징

항목	설명
정렬 방식	비교 기반 분할 정복 정렬
안정성	동일한 값의 순서 보존
추가 메모리	O(n) — temp 배열 필요
장점	항상 빠르고 예측 가능한 성능
단점	메모리 사용량이 많음
실제 사용	LinkedList, 대규모 외부 파일 정렬 등에 활용