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

1. 병합 정렬

병합 정렬은 정렬 알고리즘 중 하나로 분할 정복을 통해 정렬하는 알고리즘이다. 병합 정렬 또는 합병 정렬이라고 불린다.

---

2. 병합 정렬 성능

평균 시간복잡도	$O(N\log{N})$
최선 시간복잡도	$O(N\log{N})$
최악 시간복잡도	$O(N\log{N})$
공간복잡도	$O(N)$

$N$ 개의 원소에 대한 병합 정렬은 최선, 평균, 최악 시간복잡도 모두 $O(N\log{N})$ 으로 일관된 성능을 보여준다. 이 때문에 거의 정렬된 상태로 원소들이 주어져도 성능이 더 빨라지지 않지만 최소한의 성능은 보장한다는 장점이 있다.

병합 정렬은 주어진 원소들을 분할 후 정복(병합)하는 과정에서 임시 공간을 사용하며 이는 병합하는 두 원소들의 크기만큼이 된다. 최종 병합 과정에서는 전체 원소 크기만큼의 임시 공간이 필요하게 되고 이 때문에 병합 정렬의 공간복잡도는 $O(N)$ 이다.

병합 정렬은 병합 과정에서 동일한 가중치의 수에 대해 먼저 등장한 수를 먼저 병합할 수 있어 순서가 유지되는 안정 정렬(Stable Sort)이다.

---

3. 병합 정렬 진행 과정

병합 정렬은 주어진 원소들을 두 구간으로 분할하는 과정을 더 이상 분할할 수 없을 때까지 반복한 후 이를 임시 공간에 정렬하고 원본에 반영하는 방식으로 동작한다. 반복문을 통한 Bottom-Up 방식의 병합 정렬도 가능하지만 재귀를 통한 Top-Down 방식의 병합 정렬이 보다 일반적이라 재귀를 통한 병합 정렬로 진행하겠다.

주어진 수들이 $[4, 1, 8, 3, 6, 10, 8, 4]$ 일 경우 오름차순 병합 정렬 과정은 아래와 같이 진행된다.

먼저 주어진 원소들을 두 부분으로 분할한다. 분할은 중간 위치를 기준으로 분할하며 주어진 원소가 하나일 때까지 반복한다. 현재 1번부터 4번까지가 분할한 앞 부분이 된다.

아직 분할할 수 있으므로 두 부분으로 분할한다. 현재 1번부터 2번까지가 분할한 앞 부분이 된다.

아직 분할할 수 있으므로 두 부분으로 분할한다. 현재 1번부터 1번까지가 분할한 앞 부분이 된다.

더 이상 분할할 수 없으므로 이전으로 돌아가 이전에 분할했던 뒷 부분에 대해 똑같이 시도한다.

1번부터 2번 구간에 대한 분할이 끝났으므로 병합한다. 병합은 2칸짜리 임시 공간을 만들고 병합할 앞 부분과 뒷 부분의 첫 번째 원소부터 작은 것들을 순서대로 넣어준다.

1번부터 4번 구간에 대한 앞 부분의 병합이 완료됐다. 이제 뒷 부분에 대해 분할을 시작한다.

더 이상 분할할 수 없을 때까지 분할한다.

더 이상 분할할 수 없을 때까지 분할한다.

3번부터 4번 구간에 대한 분할이 끝났으므로 병합한다. 병합은 2칸짜리 임시 공간을 만들고 병합할 앞 부분과 뒷 부분의 첫 번째 원소부터 작은 것들을 순서대로 넣어준다.

1번부터 4번 구간에 대해 앞 부분의 병합과 뒷 부분의 병합이 각각 완료됐다. 이제 앞 부분과 뒷 부분도 병합해준다.

1번부터 8번 구간에 대해 앞 부분의 병합이 완료됐다. 이제 5번부터 8번 구간에 대해 똑같이 진행한다.

5번부터 6번 구간으로 분할해준다.

5번부터 5번 구간으로 분할해준다. 더 이상 분할할 수 없으므로 종료한다.

6번부터 6번 구간으로 분할해준다. 더 이상 분할할 수 없으므로 종료한다.

5번부터 6번 구간에 대한 분할이 끝났으므로 병합해준다.

5번부터 8번 구간의 뒷 부분에 대해 분할을 시작한다.

7번부터 7번 구간으로 분할해준다. 더 이상 분할할 수 없으므로 종료한다.

8번부터 8번 구간으로 분할해준다. 더 이상 분할할 수 없으므로 종료한다.

7번부터 8번 구간에 대한 분할이 끝났으므로 병합해준다.

5번부터 8번 구간에 대한 앞 부분 병합과 뒷 부분 병합이 각각 완료됐다. 이제 앞 부분과 뒷 부분을 병합해준다.

1번부터 8번 구간에 대한 앞 부분 병합과 뒷 부분 병합이 각각 완료됐다. 이제 앞 부분과 뒷 부분을 병합해준다. 이때 전체 구간의 길이만큼의 임시 배열이 필요해서 병합 정렬의 공간 복잡도는 $O(N)$ 이 되며 각 구간에서 동일한 가중치를 갖는 $4$, $8$ 에 대해 앞 구간의 원소를 먼저 병합하면 돼서 병합 정렬은 안정 정렬이다. 또한 분할이 $\log{N}$ 번 깊이로 발생하며 각 단계에서 $N$ 번의 병합이 이루어지므로 병합 정렬의 시간복잡도는 $O(N\log{N})$ 이다.

전체 구간에 대한 병합을 완료했으므로 병합 정렬을 종료한다. 이렇게 병합 정렬을 통해 주어진 수들을 오름차순으로 정렬하는데 성공했다.

---

4. 병합 정렬 코드

병합 정렬 [Java]

$1,000,000$ 개의 임의의 수들에 대한 정렬에서 약 0.1초정도 소요됐다.(Macbook M3 Air, JDK 21)

$O(N^2)$ 의 시간복잡도를 갖는 정렬 알고리즘에 비해 압도적으로 빠른 것을 볼 수 있다.

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

private static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;  // 더 이상 분할할 수 없으면 분할 종료

    int mid = (left + right) / 2;  // 분할점 선정

    mergeSort(arr, left, mid);  // 앞 부분 재귀적으로 분할
    mergeSort(arr, mid + 1, right);  // 뒷 부분 재귀적으로 분할
    merge(arr, left, mid, right);  // 병합
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1];  // 앞 부분과 뒷 부분을 모두 담을 수 있는 임시 공간

    int i = left;  // 앞 부분의 포인터
    int j = mid + 1;  // 뒷 부분의 포인터
    int k = 0;  // 임시 공간의 포인터

    while (i <= mid && j <= right) {
        // 앞 부분의 포인터가 가리키는 원소가 뒷 부분의 포인터가 가리키는 원소보다 작거나 같으면 임시 공간에 넣고 포인터 이동
        // 이때 같아도 앞 부분의 원소를 먼저 넣어서 안정 정렬이 됨
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        }
        // 뒷 부분의 포인터가 가리키는 원소가 앞 부분의 포인터가 가리키는 원소보다 작으면 임시 공간에 넣고 포인터 이동
        else {
            tmp[k++] = arr[j++];
        }
    }

    // 앞 부분의 남은 자투리 넣기
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }

    // 뒷 부분의 남은 자투리 넣기
    while (j <= right) {
        tmp[k++] = arr[j++];
    }

    // 병합 정렬 결과 원본에 반영
    System.arraycopy(tmp, 0, arr, left, tmp.length);
}

---

Ref

• wikipedia - 병합 정렬

---