[알고리즘] 병합 정렬 (Merge Sort)

병합 정렬 (Merge Sort) = 합병 정렬

• 분할 정복(Divide and Conquer) 방식을 사용하여 정렬을 수행하는 알고리
• 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 크기를 비교하여 정렬하면서 합병하는 방식
• 시간복잡도 : O(nlogn)
• 공간복잡도 : O(n)

병합 정렬 기본 프로세스

1. 분할(Divide) : 정렬할 배열을 반으로 나눈다. 이를 위해 배열의 중간 지점을 찾고, 중간을 기준으로 왼쪽과 오른쪽 부분 배열로 나눈다. O(logn)
2. 정복(Conquer) : 나누어진 부분 배열에 대해 재귀적으로 정렬을 수행한다. 이 단계에서는 분할된 부분 배열이 단일 원소로 이루어질 때까지 계속해서 재귀 호출을 수행한다.
3. 병합(Merge) : 정렬된 부분 배열을 병합하여 전체 배열을 생성한다. 병합할 때는 두 부분 배열을 비교하면서 작은 순서대로 원소를 선택하여 새로운 배열에 넣는다. O(n)

장점

• 안정적인 정렬이다
  • 동일한 값에 대해 상대적인 순서가 보장된다.
    
    
• 성능이 예측 가능하다.
  • 최악의 경우에도 시간 복잡도 O(nlogn)을 보장한다. 따라서 입력 데이터의 분포나 순서에 크게 영향을 받지 않고 일관된 성능을 보인다.
    
    
• 배열 뿐만 아니라 연결 리스트에도 적용할 수 있다.
  • 연결 리스트의 경우 원소를 분할하고 병합하는 과정이 배열에 비해 간다하며, 메모리 관리에 유리한 경우가 있다.

단점

• 추가적인 메모리 공간이 필요하다.
  • 재귀 호출 및 병합할 때 임시 배열을 사용하기 때문에 정렬할 배열과 같은 크기의 추가적인 메모리 공간이 필요하다. 

퀵 정렬과의 차이점

• 분할 방식 : 병합 정렬은 분할 과정에서 배열을 반으로 나누고 재귀적으로 부분 배열을 정렬한 후, 정렬된 부분 배열을 병합하여 전체 배열을 생성한다. 퀵 정렬은 분할 과정에서 피벗을 선택하고, 피벗을 기준으로 작은 값은 왼쪽에 위치시키고 큰 값을 오른쪽에 위치시킨다. 이후 재귀적으로 각 부분 배열을 정렬한다.
• 최적화 가능성 : 일반적인 병합 정렬 구현 방식에서는 병합 과정이 추가 작업 없이 수행되기 때문에 최적화를 할 수 있는 여지가 적다. 퀵 정렬은 피벗 선택 방식을 변경하여 최적화할 수 있는 경우가 있다.

병합 정렬 구현

    // 합병 정렬을 수행하는 메서드
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            // 배열이 null이거나 크기가 1 이하이면 정렬할 필요가 없으므로 리턴
            return;
        }

        // 임시 배열 생성
        int[] temp = new int[arr.length];

        // 합병 정렬 수행
        mergeSort(arr, temp, 0, arr.length - 1);
    }

    // 배열을 분할하고 병합하는 재귀적인 메서드
    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);
        }
    }

    // 두 개의 정렬된 부분 배열을 병합하는 메서드
    private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        // 임시 배열에 정렬된 값들을 복사
        for (int i = left; i <= right; i++) {
            temp[i] = arr[i];
        }

        int i = left;   // 왼쪽 부분 배열의 인덱스
        int j = mid + 1;    // 오른쪽 부분 배열의 인덱스
        int k = left;   // 정렬된 배열에 값을 삽입할 인덱스

        // 왼쪽 부분 배열과 오른쪽 부분 배열을 비교하며 작은 값을 차례로 삽입
        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                arr[k] = temp[i];
                i++;
            } else {
                arr[k] = temp[j];
                j++;
            }
            k++;
        }

        // 남은 값들을 삽입
        while (i <= mid) {
            arr[k] = temp[i];
            i++;
            k++;
        }

        while (j <= right) {
            arr[k] = temp[j];
            j++;
            k++;
        }
    }