병합정렬

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr.length <= 1) return;
        
        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];
        
        // 배열을 두 부분으로 나누기
        for (int i = 0; i < mid; i++) {
            left[i] = arr[i];
        }
        for (int i = mid; i < arr.length; i++) {
            right[i - mid] = arr[i];
        }
        
        // 재귀적으로 각 부분 정렬
        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;
        
        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++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        
        System.out.println("정렬 전 배열:");
        for (int num : arr) System.out.print(num + " ");
        System.out.println();
        
        mergeSort(arr);
        
        System.out.println("정렬 후 배열:");
        for (int num : arr) System.out.print(num + " ");
        System.out.println();
    }
}
Java
복사

시간복잡도 분석

병합 정렬의 시간복잡도는 O(n log n)입니다. 이는 다음과 같은 분석을 통해 도출됩니다:

•

분할 과정: 배열을 반으로 나누는 과정이 log n번 발생

•

병합 과정: 각 레벨에서 n개의 원소를 병합하는 데 O(n)의 시간이 소요

따라서 전체 시간복잡도는 O(n) × O(log n) = O(n log n)이 됩니다.

분할 과정

배열을 반으로 나누는 과정이 log n번 발생하는 이유는 다음과 같습니다:

첫 번째 분할: n크기의 배열을 n/2 크기로 나눔

두 번째 분할: n/2 크기의 배열들을 n/4 크기로 나눔

세 번째 분할: n/4 크기의 배열들을 n/8 크기로 나눔

이런 식으로 계속 진행되어 배열의 크기가 1이 될 때까지 분할

이처럼 매 단계마다 배열의 크기가 절반으로 줄어들기 때문에, n에서 1까지 도달하는데 필요한 분할 횟수는 log₂n이 됩니다. 예를 들어, 크기가 8인 배열은 8 → 4 → 2 → 1로 3번(log₂8 = 3)의 분할이 필요합니다.

log₂n이 되는 이유를 수학적으로 증명해보면:

크기 n인 배열이 있을 때, 각 단계마다 2로 나누어집니다.

k번 나누었을 때의 크기를 표현하면: n/2^k

마지막에는 크기가 1이 되어야 하므로:

n/2^k = 1

양변에 2^k를 곱하면:

n = 2^k

양변에 log₂를 취하면:

log₂n = k

따라서 배열이 크기 1이 될 때까지 필요한 분할 횟수 k는 log₂n이 됩니다.

log₂n에서 log n으로 표기가 정리되는 이유는 다음과 같습니다:

빅오 표기법에서는 상수를 생략합니다.

로그의 밑이 다른 경우, 다음과 같은 로그 변환 법칙이 적용됩니다:

log_a(n) = log_b(n) / log_b(a)

예를 들어, log₂n = ln(n) / ln(2) ≈ 1.443 × ln(n)

따라서 log₂n = c × log n (c는 상수) 형태로 표현할 수 있고, 빅오 표기법에서는 상수 c를 생략하여 O(log n)으로 표기합니다.

이러한 이유로 알고리즘 분석에서는 로그의 밑을 명시하지 않고 단순히 log n으로 표기하는 것이 일반적입니다.

병합 과정

병합 과정에서 O(n)의 시간이 소요되는 이유는 다음과 같습니다:

두 개의 정렬된 부분 배열을 병합할 때, 각 원소를 한 번씩 비교하고 새 배열에 복사해야 합니다.

왼쪽 배열과 오른쪽 배열의 원소들을 순차적으로 비교하면서, 더 작은 값을 결과 배열에 넣습니다.

이 과정에서 모든 원소를 한 번씩 확인하고 이동시켜야 하므로, n개의 원소에 대해 O(n)의 시간이 필요합니다.

예를 들어, 크기가 8인 배열을 병합할 때:

•

4개씩 나눈 두 부분 배열의 원소들을 순차적으로 비교

•

각 비교 후 더 작은 원소를 결과 배열에 복사

•

최악의 경우, 8개의 원소 모두를 한 번씩 비교하고 이동시켜야 함

이러한 작업이 전체 배열의 크기 n에 비례하여 증가하므로, 병합 과정의 시간복잡도는 O(n)이 됩니다.

따라서 전체 시간복잡도는 O(n) × O(log n) = O(n log n)이 됩니다.

공간복잡도

병합 정렬의 공간복잡도는 O(n)입니다. 이는 병합 과정에서 원본 배열과 같은 크기의 추가 배열이 필요하기 때문입니다.

특징

•

안정성: 안정 정렬

•

분할 정복(Divide and Conquer) 알고리즘의 대표적인 예시

•

모든 경우(최선, 평균, 최악)에 O(n log n)의 시간복잡도를 보장

•

추가 메모리 공간이 필요하다는 단점이 있음

작동 방식

배열을 절반으로 나눔

각각의 부분 배열을 재귀적으로 정렬

정렬된 두 부분 배열을 하나로 병합

이 과정을 통해 전체 배열이 정렬됩니다.