Merge Sort (합병 정렬)

합병 정렬이란?

기본적으로 합병 정렬은 '문제를 분할'하고, 분할된 문제를 '다시 정복하여 합치는' 과정이다.

• 분할 정복(Divide and Conquer) 기반으로 정렬되는 방식

정렬해야 하는 배열이나 리스트가 주어지면 분할을 반복하여 최대한 작게 쪼개어, 인접한 원소들끼리 비교해서 정렬하는 방식이다.

데이터를 '비교'하면서 저장하기 때문에 '비교 정렬'이며, 정렬 대상 데이터 외에 추가적인 공간이 필요하기 때문에 '제자리 정렬(in-place-sort)'이 아니다. 분할 정복을 기반으로 하기 때문에 최대한 문제를 작게 쪼개고 앞에서부터 합쳐나간다. 따라서 '안정정렬(Stable sort)' 알고리즘으로도 불린다.

• 만약 제자리 정렬로 구현하는 경우에는 일부 성능을 포기해야 한다.

Merge sort는 binary tree 형태로 쪼개지기 때문에 최대 깊이는 logN이 된다. 각 분할(N개) 별로 합병을 진행하므로 총 시간복잡도는 O(NlogN)이 된다.

Quick sort는 최악의 경우 O(N^2)의 시간복잡도를 가지는데, 최악의 경우를 고려할 경우 합병 정렬을 사용하는 것이 더 좋다고 한다.

합병 정렬의 특징

1. O(NlogN)의 시간복잡도

   1. 최악, 최선, 평균 모두 동일하다.

   2. 항상 일정한 성능을 보장하여 안정적인 정렬 속도를 제공한다.

2. O(N)의 공간복잡도

   1. 정렬 과정에서 임시 배열이 필요하므로, O(N)의 추가 공간이 발생한다.

3. 구현방식: 분할 정복 알고리즘 사용

   1. 분할(Divide): 입력 리스트를 거의 같은 크기의 두 부분으로 나눈다.

   2. 정복(Conquer): 재귀적으로 각 부분 리스트를 정렬한다.

   3. 결합(Combine): 정렬된 부분 리스트들을 하나의 정렬된 리스트로 병합한다.

4. 장단점

   1. 장점

      1. 퀵 정렬과 달리 pivot 선택 문제가 없어서 성능 변동이 적다.

      2. 안정적인 성능과 예측 가능한 실행으로 대규모 데이터 정렬에서 자주 사용되며, 특히 연결 리스트 정렬에 효과적이다.

   2. 단점

      1. 추가적인 메모리 사용이 요구되고, 대용량 데이터에서 메모리 사용량이 증가할 수 있다.

      2. 적은 데이터셋에서 다른 간단한 정렬 알고리즘보다 오버헤드가 클 수 있다.

합병 정렬 과정

1. 분할(Divide): 주어진 리스트를 절반으로 분할하여 부분 리스트로 나눈다.

2. 부분 리스트의 길이가 0 또는 1이 될 때까지 1번 과정을 반복한다.

3. 정복(Conquer): 인접 부분 리스트와 정렬하여 합친다.

구현

1. 리스트의 크기가 0 또는 1인 경우 이미 정렬된 리스트로 판단한다.

2. 1번에 해당하지 않고 정렬되지 않은 리스트는 비슷한 크기의 두 부분 리스트로 나눈다.

3. 각 서브 리스트를, 재귀로 합병 졍렬을 이용해서 정렬한다.

4. 두 서브 리스트를 다시 하나의 리스트로 합친다.

public class Main {

    static int N;
    static int[] arr;

    public static void main(String[] args) {
        arr = new int[] {1, 9, 8, 5, 4, 2, 3, 7, 6};
        N = arr.length;
        int[] tmp = new int[N];
        mergeSort(tmp, 0, N - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] tmp, int start, int end) {
        if (start >= end) return;
    
        int mid = (start + end) / 2;
        mergeSort(tmp, start, mid);
        mergeSort(tmp, mid + 1, end);

        int lt = start;
        int rt = mid + 1;
        int idx = start;
        while (lt <= mid || rt <= end) {
            if (rt > end || (lt <= mid && arr[lt] < arr[rt])) {
                tmp[idx] = arr[lt];
                lt++;
            } else {
                tmp[idx] = arr[rt];
                rt++;
            }
            idx++;
        }

        for (int i = start; i <= end; i++) {
            arr[i] = tmp[i];
        }
    }
    
    public static void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            
            // 왼쪽 절반 정렬
            mergeSort(arr, temp, left, mid);
            
            // 오른쪽 절반 정렬
            mergeSort(arr, temp, mid + 1, right);
            
            // 병합 과정
            // 현재 범위를 임시 배열에 복사
            for (int i = left; i <= right; i++) {
                temp[i] = arr[i];
            }
            
            int afterLeft = left;      // 왼쪽 부분의 인덱스
            int afterRight = mid + 1;   // 오른쪽 부분의 인덱스
            int k = left;      // 병합된 배열의 인덱스
            
            // 두 부분을 비교하며 병합
            while (afterLeft <= mid && afterRight <= right) {
                if (temp[afterLeft] <= temp[afterRight]) {
                    arr[k++] = temp[afterLeft++];
                } else {
                    arr[k++] = temp[afterRight++];
                }
            }
            
            // 왼쪽 부분에 남은 요소 복사
            while (afterLeft <= mid) {
                arr[k++] = temp[afterLeft++];
            }
        }
    }
}