[Algorithm] 합병정렬

[2d3k]

1. 구현방식

2. 시간, 공간복잡도

[2d3k]

1 합병정렬(Merge Sort)은 분할정복(divide and conquer) 알고리즘의 일종으로, 배열을 반으로 분할하여 각각을 재귀적으로 정렬하고, 그 결과를 합쳐서 전체를 정렬하는 알고리즘입니다.

자바로 합병정렬을 구현해보겠습니다.

public class MergeSort {

    // 두 배열을 합치는 함수
    public static void merge(int[] arr, int left, int mid, int right) {

        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }

        int i = 0, j = 0;
        int k = left;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // 분할하는 함수
    public static void mergeSort(int[] arr, int left, int right) {

        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    public static void main(String[] args) {

        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        int n = arr.length;

        mergeSort(arr, 0, n - 1);

        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

2 합병정렬의 시간복잡도는 O(nlogn)으로, 배열의 크기가 2배씩 증가하면서 나누어지고, 각 단계마다 모든 요소를 한 번씩 비교하므로, 총 nlogn번 비교하게 됩니다. 따라서 입력 데이터의 크기가 늘어날수록 합병정렬의 성능이 더욱 개선됩니다.

공간복잡도는 입력 배열을 복사해서 임시 배열을 만들어야 하기 때문에 O(n)입니다. 이는 정렬을 위해 추가적인 메모리가 필요하다는 것을 의미합니다. 따라서 합병정렬은 메모리가 충분한 경우에 사용하기 좋은 알고리즘입니다.

[hyeonayou]

1. 합병 정렬은 분할 정복기법과 재귀 알고리즘을 이용해서 정렬 알고리즘입니다. 즉, 주어진 배열을 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기순으로 재배열 하면서 원래 크기의 배열로 합칩니다.

public class MergeSorter {

    public static void mergeSort(int[] arr) {
        sort(arr, 0, arr.length);
    }

    private static void sort(int[] arr, int low, int high) {
        if (high - low < 2) {
            return;
        }

        int mid = (low + high) / 2;
        sort(arr, 0, mid);
        sort(arr, mid, high);
        merge(arr, low, mid, high);
    }

    private static void merge(int[] arr, int low, int mid, int high) {
        int[] temp = new int[high - low];
        int t = 0, l = low, h = mid;

        while (l < mid && h < high) {
            if (arr[l] < arr[h]) {
                temp[t++] = arr[l++];
            } else {
                temp[t++] = arr[h++];
            }
        }

        while (l < mid) {
            temp[t++] = arr[l++];
        }

        while (h < high) {
            temp[t++] = arr[h++];
        }

        for (int i = low; i < high; i++) {
            arr[i] = temp[i - low];
        }
    }
}

2.

절반씩 쪼개어 분할 하기에 반복의 수는 절반으로 줄기에 O(logN) 의 시간이 필요하며, 각 패스에서 병합할 때 모든 값들을 비교해야 하므로 O(N) 시간이 소모 됩니다. 따라서 총 시간 복잡도는 O(NlogN) 입니다.

두 개의 배열을 병합할 때 병합 결과를 담아 놓을 배열이 추가로 필요합니다. 따라서 공간 복잡도는 O(N) 입니다.