티스토리 뷰
목차
컴퓨터 구조의 아버지라 불리는 천재 수학자 존 폰 노이만(John von Neumann)이 1945년에 고안한 정렬 알고리즘이 있습니다. O(N^2)의 늪에 빠져있던 초기 컴퓨터 과학계에 '분할 정복(Divide and Conquer)'이라는 혁명적인 패러다임을 제시하며 정렬의 한계를 O(N log N)으로 단숨에 돌파해 낸 알고리즘, 바로 '병합 정렬(Merge Sort)'입니다. "해결하기 힘든 거대한 문제는, 해결하기 쉬운 가장 작은 단위로 잘게 쪼갠 뒤 다시 합치면서 푼다"는 제국주의의 통치 철학을 컴퓨터 알고리즘으로 완벽하게 승화시킨 병합 정렬의 예술적인 메커니즘을 분석해 봅니다.
1. Divide: 무자비하게 반으로 쪼개기
병합 정렬은 배열을 받으면 아무런 고민도 하지 않고 무조건 절반(Half)으로 쪼갭니다. 8개의 데이터가 들어오면 4개, 4개로 쪼개고, 4개는 2개, 2개로 쪼갭니다. 언제까지 쪼갤까요? 배열의 크기가 딱 1개가 될 때까지 재귀(Recursion)를 타고 끝없이 내려갑니다. 원소가 1개인 배열은 그 자체로 완벽하게 '정렬된 상태'라고 간주할 수 있기 때문입니다. 10만 개의 데이터가 들어와도 반으로 쪼개는 깊이는 $\log_2(100000)$, 즉 17번 정도밖에 되지 않습니다.
2. Conquer & Merge: 두 포인터의 우아한 결합
이제 바닥까지 쪼개진 원소들을 다시 합치면서(Merge) 위로 올라갈 차례입니다. 병합 정렬의 진짜 마법은 바로 이 '합치는 과정'에 숨어 있습니다. 이미 정렬된 두 개의 작은 배열을 하나의 큰 정렬된 배열로 합치는 작업입니다.
2-1. 투 포인터(Two Pointers) 병합 로직
왼쪽 배열 [1, 5, 8]과 오른쪽 배열 [2, 3, 9]를 합친다고 해봅시다.
- 왼쪽 배열의 맨 앞(1)과 오른쪽 배열의 맨 앞(2)을 가리키는 포인터를 둡니다.
- 둘 중 더 작은 값(1)을 임시 배열에 집어넣고, 왼쪽 포인터를 다음 칸(5)으로 옮깁니다.
- 이제 5와 2를 비교합니다. 더 작은 값(2)을 임시 배열에 넣고, 오른쪽 포인터를 다음 칸(3)으로 옮깁니다.
- 이런 식으로 두 배열 중 하나가 바닥날 때까지 비교를 반복하며 임시 배열에 차곡차곡 쌓아 올립니다.
이 병합 과정은 두 배열의 길이를 합친 것만큼만 비교하면 되므로 정확히 O(N)의 시간이 걸립니다. 트리의 높이인 $\log N$층마다 각각 O(N)의 병합 작업이 일어나므로, 전체 시간 복잡도는 O(N log N)으로 완벽하게 수렴합니다. 데이터가 역순이든 뭐든 어떠한 억까(최악의 경우)가 들어와도 무조건 반으로 쪼개므로 성능이 요동치지 않고 안정적입니다.
3. 유일한 단점: 공간 복잡도 (Extra Memory)
완벽해 보이는 병합 정렬에도 아킬레스건이 있습니다. 데이터를 합칠 때(Merge) 원본 배열 안에서 자리를 바꾸는 것이 불가능하여, 반드시 원본과 똑같은 크기의 임시 배열(Temporary Array)이 메모리에 추가로 필요하다는 점입니다. 메모리가 극도로 제한된 임베디드 시스템이나 데이터가 수십 기가바이트 단위라면 이 O(N)의 추가 공간 복잡도는 꽤 뼈아픈 페널티로 작용합니다.
1. 병합 정렬(Merge Sort)은 배열을 크기가 1이 될 때까지 반으로 쪼갠 뒤(Divide), 다시 크기 순으로 합치면서(Merge) 정렬하는 분할 정복 알고리즘입니다.
2. 데이터의 초기 상태와 완전히 무관하게 최선, 평균, 최악의 경우 모두 O(N log N)의 빠르고 안정적인 속도를 확정적으로 보장합니다.
3. 속도는 훌륭하지만, 병합 과정에서 원본 데이터와 동일한 크기의 추가 메모리 공간(O(N))이 반드시 필요하다는 단점이 있습니다.