[Algorithm] 병합 정렬(Merge Sort)

병합 정렬(Merge Sort)

출처

병합 정렬(Merge Sort)은 비교 기반 정렬 알고리즘이자 분할 정복 알고리즘 중 하나입니다.
분할 정복 알고리즘은 큰 문제를 작은 하위 문제로 나누고 각 하위 문제를 해결한 다음 그 결과를 결합하여 원래 문제를 해결하는 방식으로 진행합니다.
또한 하위 배열들을 병합하는 과정에서 투 포인터 기법이 사용됩니다.

1. 분할: 주어진 배열을 반으로 나누는 과정으로 시작하며 정렬되지 않은 배열의 중간 지점을 기준으로 나눕니다. 해당 분할 작업을 더이상 나눌수 없을 때까지 재귀적으로 반복합니다.
2. 정복: 나뉜 하위 배열들들에 대해 재귀적으로 병합 정렬 진행합니다. 각 하위 배열은 독립적으로 정렬됩니다.
3. 병합: 투 포인터 기법을 사용하여 두 정렬된 하위 배열을 하나로 합칩니다. 두 개의 포인터는 각 배열을 탐색하며 작은 값을 선택하고 정렬된 배열에 추가합니다. 이 과정에서 두 하위 배열을 결합하고 정렬된 하나의 배열을 생성합니다.

예제

출처

위 배열을 오름차순으로 정렬하기 위한 병합 정렬 알고리즘은 다음과 같이 동작합니다.

1. 먼저 해당 배열을 2개로 나눕니다.
2. 나뉘어진 배열을 각각 2개로 다시 나눕니다.
3. 나뉘어진 배열을 각각 2개로 다시 나눕니다.
4. 각 요소를 단일 요소로 나눕니다.
5. 오름차순으로 값을 정렬합니다.
6. 나우진 정렬된 배열을 하나로 병합합니다.
7. 오름차순으로 정렬된 배열이 완성됩니다.

시간 복잡도

병합 정렬은 N 개의 데이터를 분할 작업하기 위해서는 log N 번 수행합니다.
또한 두 개의 정렬된 하위 배열을 병합하는 단계에서 각 요소를 한 번씩만 비교하고 이동하기 때문에 O(n)의 시간 복잡도를 가집니다.
O(N) 작업을 log n번 해야하므로 시간복잡도는 O(N log N)이 됩니다.

코드

package io.github.ones1kk.study.sorting;

public class MergeSort {

    private static int[] sorted;

    public static void mergeSort(int[] arr, int left, int right) {
        sorted = new int[arr.length];
        for (int size = 1; size <= right; size += size) {
            for (int l = 0; l <= right - size; l += (2 * size)) {
                int low = l;
                int mid = l + size - 1;
                int high = Math.min(l + (2 * size) - 1, right);
                merge(arr, low, mid, high);
            }
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int l = left;
        int r = mid + 1;
        int idx = left;

        while (l <= mid && r <= right) {
            if (arr[l] <= arr[r]) {
                sorted[idx] = arr[l];
                idx++;
                l++;
            } else {
                sorted[idx] = arr[r];
                idx++;
                r++;
            }
        }

        if (l > mid) {
            while (r <= right) {
                sorted[idx] = arr[r];
                idx++;
                r++;
            }
        } else {
            while (l <= mid) {
                sorted[idx] = arr[l];
                idx++;
                l++;
            }
        }

        for (int i = left; i <= right; i++) {
            arr[i] = sorted[i];
        }
    }
}

좀 더 자세한 코드는 이 곳에서 확인 가능합니다.

오탈자 및 오류 내용을 댓글 또는 메일로 알려주시면, 검토 후 조치하겠습니다.