병합정렬

병합정렬

병합 정렬은 분할 정복 알고리즘의 일종으로 배열을 반으로 나눈 후 각 부분에서 재귀적으로 정렬을 수행하는 알고리즘입니다. 여러 번 반복하여 배열이 충분히 작아질 때까지 이 작업을 진행한 후, 병합 정렬을 사용하여 두 부분을 합치면서 정렬을 완성합니다.

병합 정렬과 분할 정렬의 관계

분할정렬

배열을 반으로 나누어 각 부분에서 재귀적으로 정렬을 수행합니다.

배열이 충분히 작아 더 이상 나눌 수 없을 때까지 이 과정을 반복합니다.

병합정렬

정렬된 두 개의 한위 배열을 하나로 합칩니다.

정렬된 하위 배열을 합치는 과정에서 정렬 순서를 유지하며, 작은 값을 순서대로 새로운 배열에 병합합니다.

병합 정렬 동작 과정

분할

주어진 배열을 반으로 나눕니다.

배열의 중간 지점을 찾고, 왼쪽과 오른쪽으로 나눕니다.

더 이상 나눌 수 없을 때까지 이 과정을 재귀적으로 반복합니다.

정복

각 부분 배열을 정렬합니다. 일반적으로 재귀를 사용하여 정렬합니다.

배열이 충분히 작아 더 이상 분할할 수 없을 때까지 반복합니다.

병합

정렬된 두 개의 하위 배열을 하나로 합칩니다.

두 부분 배열을 비교하여 작은 값을 순서대로 새로운 배열에 병합합니다.

정렬된 부분 배열들을 합쳐 최종적으로 정렬된 배열을 만듭니다.

병합 정렬 코드

class MergeSort {
    static int[] buff; 

    static void __mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int i;
            int center = (left + right) / 2;
            int p = 0;
            int j = 0;
            int k = left;

            __mergeSort(a, left, center);         // 전반부를 병합정렬
            __mergeSort(a, center + 1, right);    // 후반부를 병합정렬

            for (i = left; i <= center; i++)
                buff[p++] = a[i];

            while (i <= right && j < p)
                a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];

            while (j < p)
                a[k++] = buff[j++];
        }
    }
    static void mergeSort(int[] a, int n) {
        buff = new int[n];                    // 작업용 배열을 생성

        __mergeSort(a, 0, n - 1);            // 배열 전체를 병합 정렬

        buff = null;                         // 작업용 배열을 해제
    }
}