병합 정렬 (Merge Sort)
들어가는 말
병합 정렬은 배열을 더 이상 분할할 수 없을 때까지 절반씩 분할한 뒤, 각 부분 배열을 정렬하면서 다시 합치는 알고리즘이다.
하나의 큰 문제를 작은 문제로 나누어 해결한 뒤 결과를 합치는 분할 정복 알고리즘의 대표적인 예이다.
배열을 나누는 과정에서는 원소의 순서를 바꾸지 않고, 두 부분 배열을 병합하는 과정에서 값을 비교해 순서를 정한다.
시간 복잡도가 항상 O(n log n)이라 배열의 초기 상태와 관계없이 일정한 성능을 보이지만, 병합 결과를 저장할 임시 배열이 필요하다.
정렬 과정 살펴보기
8 3 6 7 2 5가 오름차순으로 정렬되는 과정을 그림으로 살펴보자.
[Divide]
[8 3 6 7 2 5]
|
+---------------+---------------+
| |
[8 3 6] [7 2 5]
| |
+-------+-------+ +-------+-------+
| | | |
[8 3] [6] [7 2] [5]
| |
+---+---+ +---+---+
| | | |
[8] [3] [7] [2]
[Merge]
[8] [3] [6] [7] [2] [5]
| | | | | |
+---+---+ | +---+---+ |
| | | |
[3 8] [6] [2 7] [5]
| | | |
+-------+-------+ +-----+------+
| |
[3 6 8] [2 5 7]
| |
+---------------+---------------+
|
[2 3 5 6 7 8]분할
병합 정렬은 배열을 원소가 하나씩 남을 때까지 절반씩 두 부분으로 나눈다.
이 과정에서는 값을 비교하거나 위치를 바꾸지 않고, 원래 배열에서 이어져 있던 구간을 더 작은 구간으로 나누기만 한다.
원소 수가 홀수라 정확히 절반으로 나눌 수 없으면 한쪽 부분 배열이 원소를 하나 더 가진다.
원소가 하나인 배열은 비교할 대상이 없으므로 그 자체로 정렬된 상태이다.
따라서 원소가 하나씩 남으면 분할을 멈추고, 이 작은 배열들을 병합하면서 더 큰 정렬된 배열을 만든다.
배열의 크기는 분할할 때마다 절반으로 줄어드니, 원소가 n개인 배열을 모두 분할하려면 약 log₂ n단계가 필요하다.
병합
실제 정렬은 나누어진 부분 배열을 다시 합치는 병합 과정에서 이루어진다.
병합할 두 부분 배열은 각각 정렬되어 있으므로, 두 배열의 맨 앞 값만 비교하면 아직 옮기지 않은 값 중 가장 작은 값을 찾을 수 있다.
두 값 중 작은 값을 결과 배열로 옮긴 뒤, 해당 배열의 다음 값과 다른 배열의 맨 앞 값을 다시 비교한다.
이 과정을 반복하면 한쪽 배열의 값을 모두 옮기게 된다.
이때 다른 배열에는 아직 옮기지 않은 값들이 정렬된 상태로 남아 있다.
남은 값들은 이미 결과 배열에 옮긴 값보다 크거나 같으므로, 결과 배열에 순서대로 옮긴다.
그러면 두 부분 배열이 하나의 정렬된 배열로 합쳐진다.
분할이 끝나면 원소가 하나인 배열부터 차례대로 병합한다.
왼쪽에서는 [8]과 [3]으로 [3 8]을 만들고, 여기에 [6]을 병합해 [3 6 8]을 만든다.
오른쪽에서는 [7]과 [2]로 [2 7]을 만들고, 여기에 [5]를 병합해 [2 5 7]을 만든다.
마지막으로 [3 6 8]과 [2 5 7]을 병합하면 [2 3 5 6 7 8]이 되고 정렬이 완료된다.
병합 정렬은 원소가 하나 남을 때까지 배열을 절반씩 나누므로, 분할 단계는 약 log₂ n번이다.
각 단계에서는 나누어진 부분 배열을 병합하며 전체 원소를 한 번씩 비교하고 옮기므로 O(n)의 비용이 든다.
따라서 전체 시간 복잡도는 단계 수 log₂ n과 단계별 비용 n을 곱한 O(n log n)이다.
배열의 초기 상태와 관계없이 같은 비용이 들기 때문에 최선, 평균, 최악의 경우 모두 O(n log n)의 시간 복잡도를 보장한다.
병합 결과를 저장하기 위해 원본 배열과 같은 크기의 임시 배열이 필요하므로 공간 복잡도는 O(n)이다.
소스 코드
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int temp[], int left, int mid, int right)
{
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while (i <= mid)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (int index = left; index <= right; index++)
arr[index] = temp[index];
}
void merge_sort_recursive(int arr[], int temp[], int left, int right)
{
if (left >= right)
return;
int mid = (left + right) / 2;
merge_sort_recursive(arr, temp, left, mid);
merge_sort_recursive(arr, temp, mid + 1, right);
merge(arr, temp, left, mid, right);
}
void merge_sort(int arr[], int size)
{
int* temp = malloc(sizeof(int) * size);
if (temp == NULL)
return;
merge_sort_recursive(arr, temp, 0, size - 1);
free(temp);
}
int main(void)
{
int arr[] = { 8, 3, 6, 7, 2, 5 };
int size = sizeof(arr) / sizeof(arr[0]);
merge_sort(arr, size);
for (int i = 0; i < size; i++)
printf("%d ", arr[i]); // Result: 2 3 5 6 7 8
return 0;
}구현 설명
merge_sort는 호출자가 직접 호출하는 함수로, 내부적으로 병합 정렬에 필요한 준비와 정리를 담당한다.
사용자가 배열과 원소 개수만 전달하면 원본 배열과 크기가 같은 임시 배열 temp를 동적으로 할당하고, merge_sort_recursive를 호출한다.
병합 정렬이 끝난 뒤에는 free로 임시 배열을 해제한다.
merge_sort_recursive는 실제 병합 정렬을 수행하며, 현재 정렬할 구간의 시작 인덱스 left와 마지막 인덱스 right를 매개변수로 받는다.
분할 과정에서는 배열을 절반씩 나누지만, 병합에 사용할 임시 배열 temp 외에 새로운 배열을 만들거나 원본 배열을 물리적으로 쪼개는 것은 아니다.
대신 인덱스 범위만 바꾸어 같은 원본 배열 안의 부분 배열을 논리적으로 표현한다.
예를 들어 원소가 6개인 원본 배열에서 left가 0이고 right가 5이면 배열 전체 범위를 나타낸다.
left가 0이고 right가 2이면 배열의 앞쪽 3개의 원소를 나타낸다.
left가 3이고 right가 5이면 배열의 뒤쪽 3개의 원소를 나타낸다.
merge_sort_recursive는 전달받은 범위에 원소가 둘 이상이면 중간 인덱스 mid를 구한다.
그런 다음 left부터 mid까지의 범위와 mid + 1부터 right까지의 범위에 대해 차례로 자신을 재귀 호출한다.
이 과정을 반복하면 각 범위에는 원소가 하나만 남고, 이때 left >= right가 되므로 호출을 종료한다.
두 부분 범위에 대한 재귀 호출이 모두 끝나면 merge를 호출하여 정렬된 두 부분 배열을 하나로 합친다.
다음으로 배열의 앞쪽 3개의 원소인 [8, 3, 6]이 이 과정을 거쳐 정렬되는 흐름을 살펴보자.
left가 0이고 right가 2이면 현재 범위는 [8, 3, 6]이다.
mid는 1이므로 먼저 left가 0이고 right가 1인 범위에 대해 재귀 호출한다.
이 호출의 현재 범위는 [8, 3]이다.
다시 범위를 나누어 left와 right가 모두 0인 범위에 대해 재귀 호출한다.
이 호출이 다루는 원소는 8 하나뿐이므로 이미 정렬된 상태이며, 함수는 종료되어 이전 호출로 돌아간다.
이어서 left와 right가 모두 1인 범위에 대해 재귀 호출하며, 이 호출도 원소 3 하나뿐이므로 바로 반환된다.
두 재귀 호출이 모두 반환되면 실행 흐름은 left가 0이고 right가 1인 호출로 돌아온다.
이제 merge로 두 부분 배열 [8]과 [3]을 합쳐 [3, 8]로 정렬한다.
이 호출이 완료되면 실행 흐름은 left가 0이고 right가 2인 호출로 돌아온다.
이어서 left와 right가 모두 2인 범위에 대해 재귀 호출한다.
이 호출이 다루는 원소는 6 하나뿐이므로 바로 반환된다.
실행 흐름이 left가 0이고 right가 2인 호출로 돌아오면 merge로 [3, 8]과 [6]을 합쳐 [3, 6, 8]로 정렬한다.
이처럼 두 부분 배열을 각각 정렬한 뒤 하나로 병합하는 과정이 재귀 호출의 역순으로 반복되며, 마지막에는 원본 배열 전체가 정렬된다.