[ Algorithm ] Merge Sort(병합 정렬)

정렬된 배열 합치기(Merging Sorted Arrays)

정렬된 배열을 합치는 과정은 매우 효율적이다

• 시간 복잡도(Time complexity): O(N)
• 공간 복잡도(Space complexity): O(N) (추가 배열 생성)

이는 정렬된 데이터에 사용할 수 있는 효율적 알고리즘의 간단한 예시이다.

정렬된 배열들의 필요성

• 우선 원본 배열을 정렬된 여러 배열로 만든다.
  • 단, 원본 배열을 정렬하면 안 됨
• 그 다음 정렬된 배열들을 앞서 언급한 방법으로 합친다.

병합 정렬(Merge Sort)

1. 입력 배열을 재귀적으로 반씩 나눠 요소 수가 1인 배열들을 만든다.
   • 요소 수가 1이므로 정렬된 배열임
   • 정확히 반씩 나누므로 재귀 깊이는 O(log N)
2. 재귀 반대 방향으로 배열을 계속 합친다.
   • 이때 정렬된 상태를 유지해야 함
   • 각 재귀 단계마다 방문하는 요소 수는 O(N)
3. 제일 상위 단계까지 합치면 정렬이 완료된다.

Java 구현

public class MergeSort {
    public static void mergeSort(int[] array) {
        if (array == null) {
            return;
        }
        if (array.length > 1) {
            int mid = array.length / 2;
            int[] leftArray = new int[mid];
            int[] rightArray = new int[array.length - mid];
            System.arraycopy(array, 0, leftArray, 0, mid);
            System.arraycopy(array, mid, rightArray, 0, array.length - mid);
            mergeSort(leftArray);
            mergeSort(rightArray);
            merge(array, leftArray, rightArray);
        }
    }

    public static void merge(int[] array, int[] leftArray, int[] rightArray) {
        int leftIndex = 0, rightIndex = 0, mergedIndex = 0;
        // 왼쪽과 오른쪽 배열을 비교, 그중 작은 값을 먼저 병합
        while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
            if (leftArray[leftIndex] < rightArray[rightIndex]) {
                array[mergedIndex++] = leftArray[leftIndex++];
            } else {
                array[mergedIndex++] = rightArray[rightIndex++];
            }
        }

        // 남은 요소들 처리
        while (leftIndex < leftArray.length) {
            array[mergedIndex++] = leftArray[leftIndex++];
        }
        while (rightIndex < rightArray.length) {
            array[mergedIndex++] = rightArray[rightIndex++];
        }
    }
}

병합 정렬의 주요 특징

• 시간 복잡도: O(N log N)
  • 분할 과정: O(log N)
  • 각 단계에서의 병합: O(N)
• 공간 복잡도: O(N) (추가 배열 사용)
• 안정적인(stable) 정렬 알고리즘
• 대용량 데이터 정렬에 효과적

병합 정렬은 분할 정복(divide and conquer) 알고리즘의 대표적인 예시로, 큰 문제를 작은 문제로 나누어 해결하는 방식을 잘 보여준다. 이 알고리즘은 특히 연결 리스트(linked list)의 정렬에 매우 효율적이며, 외부 정렬(external sorting)에도 널리 사용된다.