합병 정렬(Merge Sort)

합병 정렬(Merge Sort)

---

합병정렬(Merge Sort)은 분할정복(Divide and Conquer) 알고리즘을 기반으로 동작하는 정렬 알고리즘입니다. 합병(Merge)을 이용하면 임의의 배열을 정렬할 수 있습니다.

 

예를 들어 원소가 n개인 배열을 정렬한다고 가정하면 계속해서 반으로 분할하는 과정을 거치면 언젠가 원소가 하나인 배열이 됩니다. 하나짜리 배열은 정렬된 배열이니 합치면 정렬된 배열이 됩니다. 이런 절차를 합병정렬이라 합니다.

 

합병 정렬의 동작 원리

1. 분할(Divide) : 원소가 1개 남을 때까지 배열을 반으로 나누는 과정을 반복합니다.
2. 정복(Conquer) : 나뉜 배열을 각각 따로 정렬합니다. 
3. 병합(Combine) : 정렬한 두 배열을 합병하여 더 큰 정렬된 배열을 만듭니다.

 

합병 정렬의 특징

• 시간 복잡도 : 분할 단계는 log n 병합 단계는 O(n)이므로 O(n log n)이 됩니다.
• 공간 복잡도 : 원소가 1개인 배열이 될 때까지 분할하므로 n개의 배열 공간이 필요해 O(n)이 됩니다.

 

합병 정렬 구현 코드(Java 구현)

구현 1

class Merge {
    // 분할
    public void sort(int[] S) {
        if(S.length <= 1) { // 1. 배열의 길이가 1 이하인 경우 정렬 완료
            return;
        }

        // 2. 배열을 두 부분으로 나눔
        int mid = S.length / 2;
        // 배열을 절반으로 나누기
        int[] left = Arrays.copyOfRange(S, 0, mid);
        int[] right = Arrays.copyOfRange(S, mid, S.length);

        // 재귀적으로 정렬
        sort(left);
        sort(right);

        // 정렬된 배열을 병합
        merge(S, left, right);
    }
    
    // 병합
    public void merge(int[] S, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        // left와 right 배열의 원소를 비교하여 S 채움
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                S[k++] = left[i++];
            } else {
                S[k++] = right[j++];
            }
        }
        
        // left 배열에 남아있는 원소가 있다면 채움
        while (i < left.length) {
            S[k++] = left[i++];
        }
        
        // right 배열에 남아있는 원소가 있다면 채움
        while (j < right.length) {
            S[k++] = right[j++];
        }
    }
}

public class MergeSort {
    public static void main(String[] args) {
        int[] S = new int[] { 6, 3, 1, 5, 2, 4 };
        Merge merge = new Merge();
        merge.sort(S);
        System.out.print("합병 정렬 : ");
        for (int s : S) {
            System.out.print(s + " ");
        }
    }
}

 

구현 2

class MergeSort {
    // 합병 정렬 함수
    public void mergesort(int[] array, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2; // 중간 인덱스 계산

            // 왼쪽 절반과 오른쪽 절반을 각각 재귀적으로 정렬
            mergesort(array, low, mid);
            mergesort(array, mid + 1, high);

            // 두 부분 배열을 합병
            merge(array, low, mid, high);
        }
    }

    // 두 배열을 병합하는 함수
    public void merge(int[] array, int low, int mid, int high) {
        // 임시 배열 생성
        int[] temp = new int[high - low + 1];
        
        int i = low;   // 왼쪽 부분 배열의 시작 인덱스
        int j = mid + 1;  // 오른쪽 부분 배열의 시작 인덱스
        int k = 0;  // temp 배열의 인덱스

        // 두 배열을 비교하면서 temp 배열에 정렬된 순서대로 삽입
        while (i <= mid && j <= high) {
            if (array[i] <= array[j]) {
                temp[k] = array[i];
                i++;
            } else {
                temp[k] = array[j];
                j++;
            }
            k++;
        }

        // 왼쪽 배열의 남은 원소들 삽입
        while (i <= mid) {
            temp[k] = array[i];
            i++;
            k++;
        }

        // 오른쪽 배열의 남은 원소들 삽입
        while (j <= high) {
            temp[k] = array[j];
            j++;
            k++;
        }

        // 임시 배열의 내용을 원래 배열에 복사
        for (i = 0; i < temp.length; i++) {
            array[low + i] = temp[i];
        }
    }
}

public class MergeSortTwo {
    public static void main(String[] args) {
        int[] S = new int[] { 10, 12, 20, 27, 13, 9, 22, 25 };
        MergeSort merge = new MergeSort();
        // 배열 인덱스 범위를 올바르게 지정 (0부터 7까지)
        merge.mergesort(S, 0, S.length - 1);
        System.out.print("정렬 : ");
        for(int num : S) {
            System.out.print(num + " ");
        }
    }
}

 

합병 정렬의 장단점

장점

어느 상황에서나 시간 복잡도는 O(n log n) 입니다. 계속 반씩 나눠서 분할하기 때문에 데이터가 큰 경우에 효율적입니다.

 

단점

분할하기 때문에 추가 배열이 필요하여 O(n)의 메모리를 소모합니다. 그리고 배열을 계속 만들기 때문에 입력된 배열이 아닌 별도의 배열을 만들어서 정렬해야 합니다.

 

응용 사례

합병 정렬은 분할정복의 대표적은 예로 효율적인 시간 복잡도와 안정적인 정렬을 가지고 있습니다. 추가 메모리를 사용하는 단점이 존재하지만 매우 큰 데이터나 안전성이 요구되는 경우에 효과적입니다.