Merge Sort

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 방법을 이용한 효율적인 정렬 알고리즘이다. 이 알고리즘은 배열을 반복적으로 반으로 나누고, 더 이상 나눌 수 없을 때까지 분할한 후, 다시 합병하면서 정렬하는 방식이다. 병합 정렬은 안정 정렬에 속하며, 시간 복잡도가 O(n log n)으로 매우 효율적이다.

병합 정렬의 동작 원리

• 분할(Divide): 배열을 반으로 나누어 두 개의 부분 배열로 분할한다.
• 정복(Conquer): 각 부분 배열을 재귀적으로 병합 정렬하여 정렬된 부분 배열로 만든다.
• 결합(Combine): 두 개의 정렬된 부분 배열을 하나의 정렬된 배열로 합친다.

예제 코드

병합 정렬 구현

public class MergeSort {
    private static int[] sorted; // 임시 배열

    public static void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(a, left, mid); // 왼쪽 부분 배열 정렬
            mergeSort(a, mid + 1, right); // 오른쪽 부분 배열 정렬
            merge(a, left, mid, right); // 정렬된 부분 배열을 병합
        }
    }

    private static void merge(int[] a, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) {
            if (a[i] <= a[j]) {
                sorted[k++] = a[i++];
            } else {
                sorted[k++] = a[j++];
            }
        }

        // 왼쪽 부분 배열이 남아있다면 복사
        while (i <= mid) {
            sorted[k++] = a[i++];
        }

        // 오른쪽 부분 배열이 남아있다면 복사
        while (j <= right) {
            sorted[k++] = a[j++];
        }

        // 정렬된 배열을 원본 배열에 복사
        for (int l = left; l <= right; l++) {
            a[l] = sorted[l];
        }
    }

    public static void main(String[] args) {
        int[] arr = {6, 2, 4, 3, 7, 1, 9};
        sorted = new int[arr.length]; // 임시 배열 초기화
        mergeSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

단계별 설명

예제 배열: [6, 2, 4, 3, 7, 1, 9]
1. 분할 단계:

• 배열을 반으로 나누어 [6, 2, 4, 3]과 [7, 1, 9]로 분할한다.
• [6, 2, 4, 3]을 다시 [6, 2]와 [4, 3]으로 분할한다.
• [7, 1, 9]을 다시 [7, 1]과 [9]로 분할한다.

2. 정복 단계:

• [6, 2]을 정렬하여 [2, 6]으로 만든다.
• [4, 3]을 정렬하여 [3, 4]로 만든다.
• [7, 1]을 정렬하여 [1, 7]로 만든다.

3. 병합 단계:

• [2, 6]과 [3, 4]를 병합하여 [2, 3, 4, 6]으로 만든다.
• [1, 7]과 [9]를 병합하여 [1, 7, 9]로 만든다.
• [2, 3, 4, 6]과 [1, 7, 9]를 병합하여 최종적으로 [1, 2, 3, 4, 6, 7, 9]로 만든다.

시간 복잡도

병합 정렬의 시간 복잡도는 분할과 병합 과정에서 각각 O(log n)과 O(n)의 시간이 소요되므로 전체적으로 O(n log n)이다.

• 최악의 경우: O(n log n)
• 최선의 경우: O(n log n)
• 평균의 경우: O(n log n)

공간 복잡도

병합 정렬은 임시 배열을 사용하여 정렬된 배열을 저장하기 때문에, 추가적인 메모리 공간이 필요하다. 따라서 공간 복잡도는 O(n)이다.

장점

• 데이터의 분포에 영향을 받지 않으므로 입력 데이터가 무엇이든 정렬 시간은 동일하다.
• 크기가 큰 레코드를 정렬할 때, 특히 LinkedList를 사용하면 병합 정렬은 매우 효율적이다.
• 안정 정렬이므로 동일한 값의 원소 순서가 유지된다.

단점

• 임시 배열을 사용하므로 추가적인 메모리 공간이 필요하다.
• 제자리 정렬이 아니므로 메모리 낭비를 초래할 수 있다.
• 레코드의 크기가 큰 경우, 이동 횟수가 많아져 시간적 낭비가 발생할 수 있다.

병합 정렬의 활용

병합 정렬은 순차적인 접근이 효율적인 LinkedList 정렬에 매우 유용하다. 반면, 퀵 정렬은 임의 접근이 효율적이므로 배열 정렬에 더 적합하다. 따라서 병합 정렬은 LinkedList와 같은 자료 구조에서 유리한 성능을 보인다.

• 배열: 인덱스를 사용하여 임의 접근이 가능하므로 O(1) 시간 복잡도를 가지며, 퀵 정렬이 더 효율적일 수 있다.
• LinkedList: 순차 접근을 사용해야 하므로 O(n) 시간 복잡도를 가지며, 병합 정렬이 더 효율적이다.

So...

병합 정렬은 안정적이고 효율적인 정렬 알고리즘으로, 특히 데이터의 크기와 분포에 관계없이 일정한 성능을 보장한다. 다만, 추가적인 메모리 공간을 필요로 하므로 메모리 사용에 민감한 환경에서는 주의가 필요하다. 오늘 학습을 통해 병합 정렬의 동작 원리와 장단점을 이해하고, 이를 적절히 활용할 수 있는 상황을 파악할 수 있었다.