지금까지의 정렬 알고리즘은 모두 배열 내부에서 원소를 비교하고 이동시키며 정렬을 완성하는 방식이었습니다. 정렬을 어떻게 만들 것인가에 대한 해법이 “배열 안을 정리하는 것”에 집중되어 있었던 셈입니다.
Merge Sort는 이 접근 자체를 바꿉니다. 배열 내부를 계속 조정하는 대신, 배열을 분할하여 정렬된 구조를 먼저 만들고, 그 결과를 병합하여 정렬을 완성합니다. 즉, 정렬을 바라보는 사고 방식이 이동 중심에서 구조 중심으로 전환되는 첫 정렬입니다.
1. Merge Sort 개요 및 핵심 아이디어
Merge Sort(병합 정렬)는 Divide and Conquer(분할 정복) 방식의 대표적인 정렬입니다. 핵심 아이디어는 다음과 같이 정리할 수 있습니다.
- Divide: 배열을 반으로 계속 쪼개어 “더 작은 정렬 문제”로 분해한다. (원소 1개가 될 때까지)
- Conquer: 원소 1개짜리 배열은 비교할 대상이 없으므로 이미 정렬된 상태로 취급한다.
- Merge: 정렬된 두 배열을 “정렬된 상태를 유지한 채” 하나로 합쳐 더 큰 정렬 결과를 만든다.
여기서 중요한 점은 “정렬을 만드는 핵심 작업”이 배열 내부에서의 삽입/이동(shift)가 아니라, 정렬된 두 덩어리를 병합(merge)하는 과정이라는 것입니다.
2. Divide → Conquer → Merge 단계
1) Divide(분할)
- 배열을 반으로 나눕니다. 그리고 각 절반을 다시 반으로 나눕니다.
- 이 과정을 원소가 1개가 될 때까지 반복합니다.
- 이 단계에서는 정렬을 수행하지 않고, 단지 “더 작은 정렬 문제”로 계속 분해합니다.
2) Conquer(정복)
- 원소가 1개인 배열은 비교할 대상이 없으므로 이미 정렬된 상태입니다.
- Merge Sort의 Conquer는 여기서 복잡한 작업을 하지 않습니다.
- 정렬이 이미 완료된 최소 단위(길이 1)를 확보하는 것이 정복 단계의 의미입니다.
그리고 이 단계는 보통 코드에서 다음과 같은 형태로 나타납니다.
if (left >= right)
{
return;
}
이 조건을 만족하는 순간, 해당 구간은 더 이상 분할되지 않으며 그 자체로 “정렬된 상태”로 취급됩니다. 즉, Conquer는 별도의 처리 로직이 아니라, 재귀가 끝나는 지점 그 자체이며, 이 최소 단위가 확보되어야만 다음 단계인 Merge에서 “정렬된 입력”을 전제로 병합이 가능해집니다.
3) Merge(병합)
이제 이미 정렬된 배열 두 개를 하나로 합칩니다. 여기서 병합의 핵심은 “아무 원소나 비교하는 것”이 아니라, 각 배열에서 아직 처리되지 않은 원소 중 가장 앞에 있는 값만을 비교한다는 점입니다.
두 배열은 각각 내부적으로 이미 오름차순으로 정렬되어 있으므로, 각 배열의 앞쪽에 위치한 원소는 그 배열에서 가장 작은 후보입니다. 따라서 병합 과정에서는 Left 배열의 현재 위치(i)와 Right 배열의 현재 위치(j)에 있는 값만 비교하면 충분합니다.
비교 결과에 따라 더 작은(또는 같은) 값을 결과 배열에 넣고, 그 값을 가져온 쪽의 포인터만 한 칸 전진시킵니다. 이렇게 하면 결과 배열에는 항상 정렬된 순서가 유지된 채로 값이 하나씩 추가됩니다.
즉, 병합 과정은 다음과 같은 규칙으로 진행됩니다.
- Left와 Right 배열에서 아직 사용하지 않은 원소 중 가장 앞에 있는 값끼리 비교
- 더 작은(혹은 같은) 값을 결과 배열에 추가하고, 해당 배열의 포인터를 전진
- 한쪽 배열의 원소를 모두 사용하면, 남은 쪽 배열의 원소를 순서대로 결과에 복사
이 방식이 가능한 이유는, 두 배열이 이미 정렬되어 있기 때문입니다. 각 배열의 앞쪽 원소만 비교해도 전체에서 가장 작은 다음 값을 항상 선택할 수 있으며, 따라서 병합은 배열 전체를 다시 탐색하지 않고도 한 번의 선형 스캔으로 완료됩니다.
※ 동작을 시각적으로 확인해보기
아래 링크는 Merge Sort의 분할(Divide) → 정복(Conquer) → 병합(Merge) 과정을 단계별로 시각화해 주는 도구입니다. 배열을 계속 반으로 나누어 정렬한 뒤, 정렬된 부분 배열들을 병합하여 전체를 정렬하는 구조 중심 접근이 어떻게 동작하는지 직관적으로 확인할 수 있습니다.
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
3. 왜 O(N log N)이 되는가 (직관)
Merge Sort의 시간 복잡도는 O(N log N) 입니다. 이걸 “외워서”가 아니라 “구조로” 보면 직관이 생깁니다.
1) 분할 깊이 = log N
배열을 계속 반으로 나누면, 각 단계마다 배열의 길이는 다음과 같이 줄어듭니다.
N
N / 2
N / 4
N / 8
...
이 과정은 현재 배열의 길이를 2로 계속 나누는 것과 같습니다.
따라서 중요한 질문은 “몇 번 나누면 배열의 길이가 1이 되는가?”입니다.
이를 수식으로 표현하면 다음과 같습니다.
N / (2k) = 1
즉, 배열의 길이가 1이 되기 위해서는 2를 k번 거듭제곱한 값이 N과 같아져야 합니다.
2k = N
이 식에서 k를 구하면 다음과 같습니다.
k = log2N
이 값이 바로 배열을 원소 1개짜리로 만들기까지 필요한 분할 단계의 개수이며, Merge Sort의 재귀 호출 트리 높이가 log2N이 되는 이유입니다.
Merge Sort에서 중요한 점은, 이 분할 깊이가 입력 크기 N에 비례해서 증가하지 않고, 로그(log) 형태로 천천히 증가한다는 것입니다. 이 구조 덕분에 이후 병합 단계와 결합되어 전체 시간 복잡도가 O(N log N)으로 이어집니다.
2) 각 단계(레벨)에서 병합 총량 = N
분할 깊이가 log N이라면, 그 각 레벨에서 병합이 일어납니다. 중요한 관찰은, 어떤 레벨이든 전체 원소 N개는 “병합 과정에서 한 번씩” 결과로 들어간다는 점입니다.
예를 들어 어떤 레벨에서:
- 길이 1짜리 N개를 합치든
- 길이 2짜리 N/2개를 합치든
- 길이 4짜리 N/4개를 합치든
결국 그 레벨의 병합에서 전체 N개의 원소가 결과 배열로 한 번씩 복사됩니다. 따라서 레벨당 비용은 O(N)입니다.
정리하면:
- 레벨 수: log N
- 레벨당 병합 작업량: N
그래서 전체는 O(N log N)이 됩니다.
4. 안정 정렬(Stable Sort)인 이유
Merge Sort는 대표적인 안정 정렬(Stable Sort)입니다. 안정 정렬이라는 것은 값이 같은 원소들의 “상대적 순서”가 정렬 후에도 유지된다는 의미입니다. 병합 과정에서 안정성이 결정됩니다. Left와 Right의 현재 값이 같을 때, Left를 먼저 결과에 넣으면 원래 배열에서 Left에 있던 원소가 Right보다 앞이었으므로 그 상대 순서가 그대로 유지됩니다.
즉, 병합 비교에서:
if (leftValue <= rightValue)일 때 Left를 먼저 선택
이 규칙 하나로 안정성이 확보됩니다.
5. 추가 메모리를 사용하는 이유와 비용
Merge Sort는 병합(merge) 과정에서 정렬된 결과를 기존 배열이 아닌 “새 공간”에 써야 합니다. 두 개의 정렬된 덩어리를 합치는 동안, 원본 배열에 바로 덮어쓰기를 시작하면 아직 비교하지 않은 값이 사라질 수 있기 때문입니다. 이 때문에 일반적인 Merge Sort 구현에서는 임시 배열(temp) 또는 보조 버퍼를 사용합니다.
- 보조 배열 크기: 입력 배열과 동일한 크기 → O(N)
여기서 말하는 O(N) 메모리는 시간 복잡도가 아니라 공간 복잡도(Space Complexity)를 의미합니다. 즉, 입력 크기 N에 비례하는 추가 메모리가 필요하다는 뜻이며, 병합 단계마다 새로운 메모리가 계속 증가하는 것은 아닙니다.
일반적인 구현에서는 보조 배열을 한 번만 생성한 뒤, 모든 병합 단계에서 이를 재사용합니다. 따라서 전체 정렬 과정 동안 필요한 추가 메모리는 항상 O(N)으로 유지됩니다.
이를 비용 구조 관점에서 정리하면 다음과 같습니다.
- 비교 비용: 병합 단계에서 발생 (각 레벨마다 전체 N개 원소 비교 → O(N))
- 이동 비용: shift가 아닌 복사(copy) 형태로 발생 (각 레벨마다 O(N))
- 공간 비용: 보조 배열 하나 → O(N) (전체 과정에서 고정)
즉, Merge Sort는 배열 내부에서 반복적으로 발생하는 O(N²) 이동(shift) 비용을 피하는 대신, 추가 메모리 O(N)을 사용하여 정렬 구조를 O(N log N)으로 바꾼 정렬입니다. 이 지점에서 Merge Sort의 트레이드오프가 분명해집니다. 시간 복잡도를 낮추기 위해 공간 복잡도를 일부 희생한 정렬이라는 점이 Merge Sort의 가장 중요한 특징입니다.
6. 실행 흐름 예제로 자세히 보기
예제로 다음 배열을 정렬해 보겠습니다.
[38, 27, 43, 3, 9, 82, 10]
6.1 Divide(분할) 단계
[38, 27, 43, 3, 9, 82, 10]
|
-----------------
| |
[38, 27, 43, 3] [9, 82, 10]
| |
--------- ------
| | | |
[38,27] [43,3] [9,82] [10]
| | |
--- --- ---
| | | | | |
[38][27] [43][3] [9][82]
원소 1개짜리로 내려가면, 그 상태 자체가 정렬된 단위입니다.
6.2 Merge(병합) 단계
이제 아래에서부터 “정렬된 것끼리” 합칩니다.
(1) [38] + [27] 병합
Left = [38]
Right = [27]
비교: 38 vs 27 -> 27 선택 결과: [27]
Right 소진, Left 잔여 [38] 복사
최종: [27, 38]
(2) [43] + [3] 병합
Left = [43]
Right = [3]
비교: 43 vs 3 -> 3 선택 결과: [3]
Right 소진, Left 잔여 [43] 복사
최종: [3, 43]
(3) [27, 38] + [3, 43] 병합
Left = [27, 38]
Right = [3, 43]
비교: 27 vs 3 -> 3 선택 결과: [3]
비교: 27 vs 43 -> 27 선택 결과: [3, 27]
비교: 38 vs 43 -> 38 선택 결과: [3, 27, 38]
Left 소진, Right 잔여 [43] 복사
최종: [3, 27, 38, 43]
(4) [9] + [82] 병합
[9] + [82] -> [9, 82]
(5) [9, 82] + [10] 병합
Left = [9, 82]
Right = [10]
비교: 9 vs 10 -> 9 선택 결과: [9]
비교: 82 vs 10 -> 10 선택 결과: [9, 10]
Right 소진, Left 잔여 [82] 복사
최종: [9, 10, 82]
(6) 최종 병합: [3, 27, 38, 43] + [9, 10, 82]
Left = [3, 27, 38, 43]
Right = [9, 10, 82]
비교: 3 vs 9 -> 3 선택 결과: [3]
비교: 27 vs 9 -> 9 선택 결과: [3, 9]
비교: 27 vs 10 -> 10 선택 결과: [3, 9, 10]
비교: 27 vs 82 -> 27 선택 결과: [3, 9, 10, 27]
비교: 38 vs 82 -> 38 선택 결과: [3, 9, 10, 27, 38]
비교: 43 vs 82 -> 43 선택 결과: [3, 9, 10, 27, 38, 43]
Left 소진, Right 잔여 [82] 복사
최종: [3, 9, 10, 27, 38, 43, 82]
이 흐름을 보면 Merge Sort의 정렬은 “분할”이 아니라 병합(merge) 과정에서 실제로 만들어진다는 점이 분명해집니다.
7. C# 기반 Merge Sort 구현 코드
아래 구현은 추가 메모리(O(N)) 버퍼를 1회만 생성하고, 재귀적으로 구간을 분할한 뒤 병합하는 전형적인 형태입니다.
(안정 정렬을 위해 <= 비교에서 Left를 우선 선택합니다.)
using System;
namespace Daebak.Common.Algorithms.Sorting
{
/// <summary>
/// Merge Sort (병합 정렬)
/// - Divide and Conquer(분할 정복) 기반 정렬
/// - 평균 / 최악 시간 복잡도: O(N log N)
/// - 안정 정렬(Stable Sort)
/// - 추가 메모리 O(N) 사용
/// </summary>
public static class MergeSort
{
/// <summary>
/// 외부에서 호출되는 진입점
/// - 보조 버퍼를 1회만 생성
/// - 실제 정렬 로직은 재귀적으로 구간을 나누는 SortRange에서 수행
/// </summary>
public static void Sort(int[] array)
{
if (array == null)
{
throw new ArgumentNullException(nameof(array));
}
// 길이가 0 또는 1이면 이미 정렬된 상태
if (array.Length <= 1)
{
return;
}
// 병합 결과를 임시로 저장할 보조 버퍼
// Merge Sort는 병합 과정에서 추가 메모리가 필요함
int[] buffer = new int[array.Length];
// 전체 구간을 대상으로 분할 정렬 시작
SortRange(array, buffer, 0, array.Length - 1);
}
/// <summary>
/// 배열의 특정 구간 [left, right]를 정렬
/// - Divide 단계: 구간을 반으로 분할
/// - Conquer 단계: 원소 1개가 될 때까지 재귀 호출
/// </summary>
private static void SortRange(int[] array, int[] buffer, int left, int right)
{
// 구간에 원소가 1개 이하이면 정렬 완료
if (left >= right)
{
return;
}
// 중간 인덱스 계산 (overflow 방지 형태)
int mid = left + ((right - left) / 2);
// 왼쪽 절반 정렬
SortRange(array, buffer, left, mid);
// 오른쪽 절반 정렬
SortRange(array, buffer, mid + 1, right);
// 두 개의 "정렬된 구간"을 병합
Merge(array, buffer, left, mid, right);
}
/// <summary>
/// 두 개의 정렬된 구간을 하나의 정렬된 구간으로 병합
/// - [left, mid] 와 [mid+1, right] 는 이미 정렬된 상태
/// - 실제 정렬 비용(비교 + 복사)이 발생하는 핵심 단계
/// </summary>
private static void Merge(int[] array, int[] buffer, int left, int mid, int right)
{
// 왼쪽 구간의 시작 인덱스
int i = left;
// 오른쪽 구간의 시작 인덱스
int j = mid + 1;
// 결과를 저장할 buffer의 인덱스
int k = left;
// 두 구간 모두 원소가 남아 있는 동안 비교
while (i <= mid && j <= right)
{
// <= 를 사용하면 값이 같은 경우 왼쪽을 먼저 선택
// → 원래 순서를 유지하므로 안정 정렬이 보장됨
if (array[i] <= array[j])
{
buffer[k] = array[i];
k++;
i++;
}
else
{
buffer[k] = array[j];
k++;
j++;
}
}
// 왼쪽 구간에 남은 원소가 있다면 그대로 복사
while (i <= mid)
{
buffer[k] = array[i];
k++;
i++;
}
// 오른쪽 구간에 남은 원소가 있다면 그대로 복사
while (j <= right)
{
buffer[k] = array[j];
k++;
j++;
}
// 병합 결과를 원본 배열의 해당 구간에 반영
// 이 시점에서 [left, right] 구간은 완전히 정렬됨
for (int idx = left; idx <= right; idx++)
{
array[idx] = buffer[idx];
}
}
}
}
- 이 구현에서는 배열 내부에서 값을 밀어내는 이동(shift)은 발생하지 않습니다.
- 대신 병합 단계에서 결과를 보조 버퍼(buffer)에 순서대로 복사하고, 마지막에 해당 구간을 원본 배열에 한 번에 덮어씁니다.
- 즉, 비용의 핵심은 비교 + 복사(copy)이며, 이를 재귀의 각 레벨마다 O(N)씩 수행합니다.
8. Unity 환경에서 테스트 해보기
using UnityEngine;
using Daebak.Common.Algorithms.Sorting;
public class Test_MergeSort : MonoBehaviour
{
private void Start()
{
int[] data = new int[] { 38, 27, 43, 3, 9, 82, 10 };
Debug.Log("Before Sort : " + string.Join(", ", data));
MergeSort.Sort(data);
Debug.Log("After Sort : " + string.Join(", ", data));
}
}
출력 결과
Before Sort : 38, 27, 43, 3, 9, 82, 10
After Sort : 3, 9, 10, 27, 38, 43, 829. 마무리 및 다음 단계
Merge Sort는 “배열 내부 이동(shift)으로 정렬을 만드는 방식”에서 벗어나, 분할 정복으로 정렬된 덩어리를 만들어 병합하는 방식으로 사고가 전환되는 첫 정렬입니다. 이로써 Shell Sort까지 이어지던 O(N²) 계열의 정렬 흐름을 넘어, O(N log N) 계열 정렬을 이해하기 위한 기준점이 됩니다.
다만 Merge Sort는 그 대가로 추가 메모리 O(N)을 사용합니다. 즉, 정렬의 비용 구조가 “비교 / 이동(shift)” 중심에서 “비교 / 복사(copy) / 메모리” 중심으로 달라진다는 점이 이 정렬의 가장 중요한 특징입니다.
다음 문서에서는 또 다른 방식으로 O(N log N)을 달성하는 정렬인 Quick Sort를 다룰 예정입니다. Merge Sort가 “정렬된 것을 병합하여 완성하는 방식”이었다면, Quick Sort는 분할 과정에서 정렬을 진행하여 추가 병합 없이 정렬을 완성하는 방식을 사용합니다. 구체적인 동작 방식과 비용 구조는 다음 문서에서 살펴보겠습니다.
※ 다음 글에서는 Quick Sort를 살펴보며, 기준 값(pivot)을 중심으로 데이터를 분할하는 방식이 평균적으로 매우 빠른 정렬 성능을 만들어내는 이유와 그 특성을 중심으로 정리합니다.
'자료 구조' 카테고리의 다른 글
| Unity 개발자를 위한 C# Quick Sort(퀵 정렬) 구현 (0) | 2026.01.18 |
|---|---|
| 대박 게임 개발 연구소(Daebak Game Dev Lab) 소개 (0) | 2026.01.15 |
| Unity 개발자를 위한 C# Shell Sort(셸 정렬) 구현 (0) | 2026.01.15 |
| Unity 개발자를 위한 C# Insertion Sort(삽입 정렬) 구현 (0) | 2026.01.14 |
| Unity 개발자를 위한 C# Selection Sort(선택 정렬) 구현 (0) | 2026.01.14 |
