고급 정렬: 퀵·병합·힙 정렬이 O(n log n)인 이유와 선택 기준
이 글의 핵심
세 알고리즘 모두 평균 O(n log n)이지만 최악 케이스, 추가 메모리, 안정성에서 성격이 다릅니다. Quick Select로 K번째 수 찾기, K개 정렬 배열 병합, 메모리에 다 올라가지 않는 데이터의 외부 정렬 같은 응용과 RecursionError 같은 흔한 문제의 해결법까지 다룹니다.
시리즈 안내
들어가며
버블·선택·삽입 정렬은 O(n²)이라 원소가 수천 개만 넘어도 비교 횟수가 수백만 단위로 늘어납니다. 퀵·병합·힙 정렬은 분할 정복이나 힙 구조로 이를 O(n log n)으로 줄이며, 언어 내장 정렬도 이 알고리즘들을 조합해 만듭니다. 삽입 정렬은 작은 구간에서 상수 비용이 낮아서, 내장 정렬이 구간이 충분히 작아지면 삽입 정렬로 전환하는 식으로 여전히 쓰입니다.
세 알고리즘이 모두 O(n log n)인 이유는 같은 그림으로 설명됩니다. 배열을 반씩 나누면 크기 1이 될 때까지 약 log₂n 단계가 필요하고, 각 단계에서 모든 원소를 한 번씩 비교하거나 옮기는 데 O(n)이 듭니다. 그래서 전체 작업량은 “단계 수 × 단계당 작업” = n log n이 됩니다. 퀵 정렬은 먼저 나누고(분할) 나중에 할 일이 없고, 병합 정렬은 대충 나누고 나중에 합치는(병합) 데 일을 몰아 둔다는 차이가 있을 뿐입니다. 퀵 정렬의 최악이 O(n²)인 것도 같은 그림으로 이해할 수 있습니다. 피벗이 매번 최솟값이면 반으로 나뉘지 않고 한 개씩만 떨어져 나가므로 단계 수가 log n이 아니라 n이 됩니다.
또 한 가지 알아 둘 사실은 비교 기반 정렬은 최악의 경우 O(n log n)보다 빠를 수 없다는 하한입니다. n개 원소의 가능한 순서는 n!가지이고, 비교 한 번은 가능성을 최대 절반으로 줄이므로 최소 log₂(n!) ≈ n log n번의 비교가 필요합니다. 계수 정렬이나 기수 정렬이 O(n)에 가까운 이유는 비교 대신 값 자체를 인덱스로 쓰기 때문이며, 그 대신 값의 범위가 제한된 정수 같은 조건이 붙습니다.
퀵 정렬 (Quick Sort)
알고리즘 원리
분할 정복:
- 피벗 선택 (보통 중간 또는 마지막 원소)
- 피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 분할
- 왼쪽과 오른쪽을 재귀적으로 정렬 시각화:
[5, 2, 8, 1, 9, 3]
피벗 = 5
[2, 1, 3] 5 [8, 9]
↓ ↓
[1, 2, 3] [8, 9]
최종: [1, 2, 3, 5, 8, 9]Python 구현 (새 리스트)
def quick_sort(arr):
"""
퀵 정렬 (새 리스트 생성)
- 읽기 쉬운 구현
- 공간 복잡도 O(n)
"""
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# 테스트
arr = [5, 2, 8, 1, 9, 3]
print(quick_sort(arr)) # [1, 2, 3, 5, 8, 9]이 버전은 원리를 보여 주기에는 좋지만, 매 단계마다 리스트를 세 번 훑고 새 리스트를 만들기 때문에 메모리 사용이 많고 in-place 버전보다 상수 배로 느립니다. 대신 값이 피벗과 같은 원소를 middle로 따로 모으기 때문에, 같은 값이 많은 입력에서도 퇴화하지 않는다는 장점이 있습니다. 아래 in-place 버전에서 이 성질을 얻으려면 3-way 파티션이 따로 필요합니다.
Python 구현 (In-place)
def quick_sort_inplace(arr, low, high):
"""
퀵 정렬 (in-place)
- 공간 복잡도: 평균 O(log n), 분할이 치우치면 최악 O(n) 재귀 스택
- 실무에서 선호
"""
if low < high:
pi = partition(arr, low, high)
quick_sort_inplace(arr, low, pi - 1)
quick_sort_inplace(arr, pi + 1, high)
def partition(arr, low, high):
"""
Lomuto 파티션 스킴
- 피벗: arr[high]
- i: 피벗보다 작은 영역의 끝
"""
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# 사용
arr = [5, 2, 8, 1, 9, 3]
quick_sort_inplace(arr, 0, len(arr) - 1)
print(arr) # [1, 2, 3, 5, 8, 9]Lomuto 파티션은 i를 “피벗보다 작은 원소 구역의 마지막 위치”로 유지합니다. j가 앞에서부터 훑다가 피벗보다 작은 원소를 만나면 구역을 한 칸 늘리고(i += 1) 그 자리로 교환해 넣습니다. 루프가 끝나면 arr[low..i]는 모두 피벗보다 작고 arr[i+1..high-1]은 피벗 이상이므로, 피벗을 i + 1에 넣으면 피벗은 최종 위치에 고정됩니다. 이 “피벗 하나가 매 분할마다 제자리를 찾는다”는 성질이 뒤의 Quick Select의 기반입니다.
Lomuto는 이해하기 쉽지만 교환 횟수가 많고, 모든 원소가 같은 배열에서 arr[j] < pivot이 한 번도 참이 되지 않아 매번 한쪽으로만 분할되어 O(n²)이 됩니다. 두 포인터가 양 끝에서 좁혀 오는 Hoare 파티션은 교환이 약 3배 적고 같은 값이 많을 때도 균형 있게 나누지만, 반환값이 피벗의 최종 위치가 아니어서 재귀 범위를 (low, p), (p+1, high)로 잡아야 하는 등 경계 실수가 잦습니다. 코딩 테스트에서 직접 구현한다면 Lomuto에 랜덤 피벗을 붙이는 것이 가장 실수가 적습니다.
C++ 구현 (In-place)
#include <vector>
#include <iostream>
void quickSort(std::vector<int>& arr, int low, int high);
int partition(std::vector<int>& arr, int low, int high);
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j) {
if (arr[j] < pivot) {
++i;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
int main() {
std::vector<int> arr = {5, 2, 8, 1, 9, 3};
quickSort(arr, 0, arr.size() - 1);
for (int num : arr) {
std::cout << num << " ";
}
// 출력: 1 2 3 5 8 9
return 0;
}시간복잡도
- 최선: O(n log n) — 피벗이 중앙값에 가까울 때
- 평균: O(n log n)
- 최악: O(n²) — 위 코드처럼 마지막 원소를 피벗으로 쓰면 이미 정렬되었거나 역순인 입력에서 발생
- 공간: O(log n) — 재귀 스택
- 안정: X (같은 값의 순서 보장 안 됨)
최악 케이스 방지
랜덤 피벗:
import random
def partition_random(arr, low, high):
random_idx = random.randint(low, high)
arr[random_idx], arr[high] = arr[high], arr[random_idx]
return partition(arr, low, high)3-way 파티션 (중복 값 많을 때):
def quick_sort_3way(arr, low, high):
if low >= high:
return
lt, gt = low, high
pivot = arr[low]
i = low + 1
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1
else:
i += 1
quick_sort_3way(arr, low, lt - 1)
quick_sort_3way(arr, gt + 1, high)3-way 파티션(Dijkstra의 네덜란드 국기 문제 풀이)은 배열을 < pivot, == pivot, > pivot 세 구역으로 나누고, 가운데 구역은 이미 제자리이므로 재귀에서 제외합니다. 값의 종류가 몇 개 안 되는 입력(성별, 등급, 0/1 플래그로 정렬)에서는 재귀 대상이 빠르게 줄어 O(n)에 가까워집니다. 랜덤 피벗은 “정렬된 입력” 문제를, 3-way 파티션은 “중복 값” 문제를 해결하므로 서로 대체재가 아니라 함께 쓰는 기법입니다. 위 코드는 설명을 위해 arr[low]를 피벗으로 쓰지만, 실제로는 먼저 무작위 원소를 low로 교환해 두는 것이 좋습니다.
병합 정렬 (Merge Sort)
알고리즘 원리
분할 정복:
- 배열을 절반으로 분할
- 각 절반을 재귀적으로 정렬
- 정렬된 두 배열을 합병 시각화:
[5, 2, 8, 1]
↓ 분할
[5, 2] [8, 1]
↓ 분할
[5] [2] [8] [1]
↓ 합병
[2, 5] [1, 8]
↓ 합병
[1, 2, 5, 8]Python 구현 (새 리스트)
def merge_sort(arr):
"""
병합 정렬 (새 리스트 생성)
- 안정 정렬
- 항상 O(n log n)
"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
"""
두 정렬된 배열 합병
"""
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# 테스트
arr = [5, 2, 8, 1, 9, 3]
print(merge_sort(arr)) # [1, 2, 3, 5, 8, 9]Python 구현 (In-place)
def merge_sort_inplace(arr, left, right):
"""
병합 정렬 (원본 배열에 결과를 씀)
- 새 리스트를 반환하지는 않지만, 병합마다 임시 배열을 만들므로 추가 공간 O(n)
- 재귀 스택은 O(log n)
"""
if left < right:
mid = (left + right) // 2
merge_sort_inplace(arr, left, mid)
merge_sort_inplace(arr, mid + 1, right)
merge_inplace(arr, left, mid, right)
def merge_inplace(arr, left, mid, right):
"""
두 정렬된 구간 합병
"""
left_arr = arr[left:mid + 1]
right_arr = arr[mid + 1:right + 1]
i = j = 0
k = left
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] <= right_arr[j]:
arr[k] = left_arr[i]
i += 1
else:
arr[k] = right_arr[j]
j += 1
k += 1
while i < len(left_arr):
arr[k] = left_arr[i]
i += 1
k += 1
while j < len(right_arr):
arr[k] = right_arr[j]
j += 1
k += 1
# 사용
arr = [5, 2, 8, 1, 9, 3]
merge_sort_inplace(arr, 0, len(arr) - 1)
print(arr) # [1, 2, 3, 5, 8, 9]C++ 구현
#include <vector>
#include <iostream>
void mergeSort(std::vector<int>& arr, int left, int right);
void merge(std::vector<int>& arr, int left, int mid, int right);
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void merge(std::vector<int>& arr, int left, int mid, int right) {
std::vector<int> leftArr(arr.begin() + left, arr.begin() + mid + 1);
std::vector<int> rightArr(arr.begin() + mid + 1, arr.begin() + right + 1);
int i = 0, j = 0, k = left;
while (i < leftArr.size() && j < rightArr.size()) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < leftArr.size()) {
arr[k++] = leftArr[i++];
}
while (j < rightArr.size()) {
arr[k++] = rightArr[j++];
}
}
int main() {
std::vector<int> arr = {5, 2, 8, 1, 9, 3};
mergeSort(arr, 0, arr.size() - 1);
for (int num : arr) {
std::cout << num << " ";
}
// 출력: 1 2 3 5 8 9
return 0;
}시간복잡도
- 최선: O(n log n)
- 평균: O(n log n)
- 최악: O(n log n) — 입력 순서와 무관
- 공간: O(n) — 임시 배열
- 안정: O (같은 값의 순서 유지)
병합 정렬의 안정성은 merge의 <= 한 글자에서 나옵니다. 왼쪽과 오른쪽 값이 같을 때 왼쪽을 먼저 가져오므로 원래 앞에 있던 원소가 결과에서도 앞에 옵니다. 이것을 <로 바꾸면 같은 값에서 오른쪽이 먼저 나와 정렬 결과는 맞는데 안정성만 조용히 깨집니다. 테스트 데이터에 중복 값이 없으면 발견되지 않는 버그라서, 안정성이 중요한 코드라면 “같은 키, 다른 식별자”를 가진 테스트 케이스를 꼭 넣어야 합니다.
병합 정렬은 배열보다 연결 리스트에서 더 빛납니다. 연결 리스트는 노드 포인터만 바꿔서 병합할 수 있어 추가 배열이 필요 없고, 퀵 정렬이나 힙 정렬처럼 임의 위치 접근이 필요하지 않기 때문입니다. std::list::sort가 병합 정렬로 구현되는 이유입니다. 또 순차 읽기만 하므로 아래 외부 정렬처럼 디스크 데이터를 다룰 때도 기본 구조가 됩니다.
힙 정렬 (Heap Sort)
알고리즘 원리
최대 힙 구조:
- 배열을 최대 힙으로 변환 (heapify)
- 루트(최대값)를 배열 끝으로 이동
- 힙 크기를 줄이고 다시 heapify
- 반복 시각화:
[5, 2, 8, 1, 9, 3]
↓ heapify
9
/ \
5 8
/ \ /
1 2 3
추출: 9 → 힙 [8, 5, 3, 1, 2] + [9]
추출: 8 → [5, 2, 3, 1] + [8, 9]
...
최종: [1, 2, 3, 5, 8, 9]Python 구현 (heapq 사용)
import heapq
def heap_sort(arr):
"""
힙 정렬 (heapq 사용)
- 최소 힙 사용
- 공간 O(n)
"""
heap = []
for num in arr:
heapq.heappush(heap, num)
result = []
while heap:
result.append(heapq.heappop(heap))
return result
# 테스트
arr = [5, 2, 8, 1, 9, 3]
print(heap_sort(arr)) # [1, 2, 3, 5, 8, 9]heappush를 n번 호출해 힙을 만들면 O(n log n)이 들지만, 리스트를 복사한 뒤 heapq.heapify(heap)를 한 번 호출하면 O(n)에 힙을 만들 수 있습니다. 아래 in-place 구현의 “최대 힙 구성” 루프가 바로 그 O(n) 방식입니다. 잎 노드(배열의 뒤쪽 절반)는 이미 크기 1짜리 힙이므로 n // 2 - 1부터 거꾸로 내려오며 heapify하면 되고, 대부분의 노드가 낮은 높이에 있어서 전체 합이 O(n)으로 수렴합니다.
Python 구현 (In-place)
def heap_sort_inplace(arr):
"""
힙 정렬 (in-place)
- 최대 힙 사용
- 공간 O(1)
"""
n = len(arr)
# 최대 힙 구성
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 하나씩 추출
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
def heapify(arr, n, i):
"""
최대 힙 속성 유지
- i: 현재 노드
- n: 힙 크기
"""
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
# 사용
arr = [5, 2, 8, 1, 9, 3]
heap_sort_inplace(arr)
print(arr) # [1, 2, 3, 5, 8, 9]C++ 구현
#include <vector>
#include <algorithm>
#include <iostream>
void heapify(std::vector<int>& arr, int n, int i);
void heapSort(std::vector<int>& arr);
void heapify(std::vector<int>& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; --i) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; --i) {
std::swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
std::vector<int> arr = {5, 2, 8, 1, 9, 3};
heapSort(arr);
for (int num : arr) {
std::cout << num << " ";
}
// 출력: 1 2 3 5 8 9
return 0;
}시간복잡도
- 최선: O(n log n)
- 평균: O(n log n)
- 최악: O(n log n)
- 공간: O(1) — in-place 가능
- 안정: X
힙 정렬은 최악 O(n log n)과 O(1) 추가 공간을 동시에 보장하는 대표적인 알고리즘이지만, 실제 실행 속도는 보통 퀵 정렬보다 느립니다. 원인은 메모리 접근 패턴입니다. heapify는 인덱스 i에서 2i+1로 점프하므로 힙이 커질수록 부모와 자식이 서로 다른 캐시 라인에 놓이고, 매 단계가 캐시 미스가 되기 쉽습니다. 퀵 정렬의 파티션은 배열을 앞에서부터 순차적으로 훑기 때문에 CPU 프리페처가 잘 동작합니다. 그래서 힙 정렬은 단독으로 쓰이기보다, Introsort에서 “퀵 정렬의 재귀가 너무 깊어졌을 때 최악을 막는 안전망”으로 쓰입니다.
정렬 비교
알고리즘 비교표
| 알고리즘 | 최선 | 평균 | 최악 | 공간 | 안정 | 특징 |
|---|---|---|---|---|---|---|
| 퀵 | O(n log n) | O(n log n) | O(n²) | O(log n) | X | 평균 가장 빠름 |
| 병합 | O(n log n) | O(n log n) | O(n log n) | O(n) | O | 항상 일정 |
| 힙 | O(n log n) | O(n log n) | O(n log n) | O(1) | X | In-place |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | O | Python 기본 |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | X | C++ 기본 |
선택 가이드
| 상황 | 추천 정렬 | 이유 |
|---|---|---|
| 평균 케이스 최적화 | 퀵 | 캐시 효율 좋음 |
| 최악 케이스 보장 | 병합 | 항상 O(n log n) |
| 메모리 제약 | 힙 | In-place (O(1)) |
| 안정 정렬 필요 | 병합 | 순서 유지 |
| 실무 (Python) | sorted() | Timsort (최적화됨) |
| 실무 (C++) | std::sort() | Introsort (최적화됨) |
내장 정렬은 무엇을 더 하는가
Python의 Timsort는 실제 데이터에 이미 정렬된 구간(run)이 많다는 점을 이용합니다. 배열을 훑으며 오름차순이나 내림차순 구간을 찾아 run으로 삼고, 짧은 run은 삽입 정렬로 늘린 뒤, run끼리 병합합니다. 그래서 거의 정렬된 데이터나 “정렬된 목록 뒤에 몇 개 추가”한 데이터에서 O(n)에 가깝게 동작하고, 병합 기반이라 안정 정렬입니다. C++의 std::sort는 보통 Introsort로 구현됩니다. 퀵 정렬로 시작하되 재귀 깊이가 약 2 log n을 넘으면 힙 정렬로 전환해 최악 O(n log n)을 보장하고, 구간이 작아지면(구현마다 16개 안팎) 삽입 정렬로 마무리합니다. 안정성이 필요하면 C++에서는 std::stable_sort를 따로 써야 합니다.
이 때문에 Python으로 퀵 정렬을 직접 구현해 sorted()와 비교하면 훨씬 느린 것이 정상입니다. sorted()는 C로 구현되어 있어 원소마다 바이트코드를 실행하는 인터프리터 오버헤드가 없기 때문입니다. 코딩 테스트에서 “정렬 알고리즘을 직접 구현하라”는 조건이 없다면 내장 정렬을 쓰고, 직접 구현은 Quick Select처럼 정렬의 일부 단계만 필요한 문제나 비교 기준을 커스터마이즈하는 데 원리를 활용하는 편이 맞습니다.
실무 사례
사례 1: K번째로 큰 수 (Quick Select)
문제: LeetCode 215 - Kth Largest Element 아이디어: 퀵 정렬의 파티션만 사용해 평균 O(n)
Python 구현
import random
class Solution:
def findKthLargest(self, nums: list[int], k: int) -> int:
"""
Quick Select: 평균 O(n), 최악 O(n²)
"""
def partition(left, right):
pivot_idx = random.randint(left, right)
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
pivot = nums[right]
i = left
for j in range(left, right):
if nums[j] >= pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[right] = nums[right], nums[i]
return i
left, right = 0, len(nums) - 1
k_idx = k - 1
while left <= right:
pi = partition(left, right)
if pi == k_idx:
return nums[pi]
elif pi < k_idx:
left = pi + 1
else:
right = pi - 1
return -1
# 테스트
sol = Solution()
print(sol.findKthLargest([3, 2, 1, 5, 6, 4], 2)) # 5시간 복잡도: 평균 O(n), 최악 O(n²)
Quick Select가 평균 O(n)인 이유는 퀵 정렬과 달리 한쪽만 재귀하기 때문입니다. 분할 후 k번째 위치가 피벗의 왼쪽에 있으면 오른쪽은 버리므로, 평균적으로 n + n/2 + n/4 + … ≈ 2n번만 비교합니다. 위 코드는 큰 값부터 앞에 오도록 >=로 분할해서 “k번째로 큰 수”의 인덱스를 k - 1로 바로 쓸 수 있게 했습니다. LeetCode 215에서 모든 값이 같은 큰 테스트 케이스가 추가된 뒤로 Lomuto 기반 Quick Select가 시간 초과를 받는 경우가 있는데, 앞의 3-way 파티션을 적용하거나 heapq.nlargest(k, nums)[-1](O(n log k))를 쓰면 해결됩니다. C++에는 같은 일을 하는 std::nth_element가 있습니다.
사례 2: 정렬된 배열 합치기 (Merge K Sorted Arrays)
문제: k개의 정렬된 배열을 하나로 합치기
Python 구현 (힙 사용)
import heapq
def merge_k_sorted_arrays(arrays):
"""
K개 정렬 배열 합병
- 시간: O(N log k), N은 전체 원소 수
"""
heap = []
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
result = []
while heap:
val, arr_idx, elem_idx = heapq.heappop(heap)
result.append(val)
if elem_idx + 1 < len(arrays[arr_idx]):
next_val = arrays[arr_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, arr_idx, elem_idx + 1))
return result
# 테스트
arrays = [
[1, 4, 7],
[2, 5, 8],
[3, 6, 9]
]
print(merge_k_sorted_arrays(arrays))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]시간 복잡도: O(N log k) — N은 전체 원소 수, k는 배열 개수
힙에 (값, 배열 번호, 원소 번호) 튜플을 넣는 이유는 값이 같을 때 튜플의 다음 원소로 비교가 넘어가기 때문입니다. 값만 넣으면 어느 배열에서 왔는지 알 수 없고, 배열 번호 없이 (값, 노드 객체)를 넣으면 값이 같을 때 노드끼리 비교하려다 TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'가 납니다. LeetCode 23(Merge k Sorted Lists)에서 자주 만나는 에러로, 중간에 인덱스를 끼워 넣으면 해결됩니다. Python 표준 라이브러리의 heapq.merge(*arrays)가 같은 일을 지연 평가로 해 줍니다.
사례 3: 외부 정렬 (External Sort)
시나리오: 메모리에 담을 수 없는 대용량 파일 정렬
Python 구현
import heapq
import os
def external_sort(input_file, output_file, chunk_size=1000):
"""
외부 정렬
1. 파일을 청크로 나눠 정렬 후 임시 파일 저장
2. 임시 파일들을 병합 정렬
"""
temp_files = []
# 1단계: 청크 정렬
with open(input_file, 'r') as f:
chunk = []
for i, line in enumerate(f):
chunk.append(int(line.strip()))
if len(chunk) >= chunk_size:
chunk.sort()
temp_file = f'temp_{len(temp_files)}.txt'
with open(temp_file, 'w') as tf:
for num in chunk:
tf.write(f'{num}\n')
temp_files.append(temp_file)
chunk = []
if chunk:
chunk.sort()
temp_file = f'temp_{len(temp_files)}.txt'
with open(temp_file, 'w') as tf:
for num in chunk:
tf.write(f'{num}\n')
temp_files.append(temp_file)
# 2단계: K-way 병합
heap = []
file_handles = []
for i, temp_file in enumerate(temp_files):
f = open(temp_file, 'r')
file_handles.append(f)
line = f.readline()
if line:
heapq.heappush(heap, (int(line.strip()), i))
with open(output_file, 'w') as out:
while heap:
val, file_idx = heapq.heappop(heap)
out.write(f'{val}\n')
line = file_handles[file_idx].readline()
if line:
heapq.heappush(heap, (int(line.strip()), file_idx))
# 정리
for f in file_handles:
f.close()
for temp_file in temp_files:
os.remove(temp_file)
# 사용 예시
# external_sort('large_input.txt', 'sorted_output.txt', chunk_size=10000)시간 복잡도: O(N log N) — N은 전체 원소 수
외부 정렬의 실제 비용은 비교 횟수보다 디스크 I/O 횟수가 좌우합니다. 청크를 크게 잡을수록 임시 파일 수가 줄고 병합 단계가 가벼워지므로, chunk_size는 가용 메모리에 들어가는 한 크게 잡는 것이 좋습니다. 이 예제는 설명용이라 임시 파일 이름을 temp_0.txt처럼 고정했는데, 같은 디렉터리에서 두 번 동시에 실행하면 서로의 파일을 덮어씁니다. 실제로는 tempfile.NamedTemporaryFile이나 tempfile.mkdtemp()를 쓰고, 예외가 나도 파일이 정리되도록 try/finally로 감싸야 합니다. 임시 파일이 수천 개가 되면 운영체제의 열린 파일 수 제한(OSError: [Errno 24] Too many open files)에 걸리므로, 그때는 한 번에 수백 개씩 여러 단계로 병합합니다. 리눅스의 sort 명령이 내부적으로 이 방식을 쓰므로, 한 번 정렬하고 끝나는 작업이라면 sort -n -S 2G big.txt 같은 명령이 가장 빠른 해결책인 경우도 많습니다.
트러블슈팅
문제 1: 퀵 정렬 최악 케이스 (O(n²))
증상:
arr = list(range(100000)) # 이미 정렬됨
# 퀵 정렬 실행 → 시간 초과원인: 피벗이 항상 최소/최대값 해결 1: 랜덤 피벗
import random
def partition_random(arr, low, high):
random_idx = random.randint(low, high)
arr[random_idx], arr[high] = arr[high], arr[random_idx]
return partition(arr, low, high)해결 2: Median-of-Three
def partition_median_of_three(arr, low, high):
mid = (low + high) // 2
# low, mid, high를 정렬 → arr[low] <= arr[mid] <= arr[high]
if arr[low] > arr[mid]:
arr[low], arr[mid] = arr[mid], arr[low]
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
# 중앙값은 이제 mid에 있음 → Lomuto가 피벗으로 쓰는 high로 옮김
# (이 교환이 없으면 최댓값이 피벗이 되어 오히려 최악 분할)
arr[mid], arr[high] = arr[high], arr[mid]
return partition(arr, low, high)Median-of-Three는 정렬된 입력과 역순 입력에서 정확히 중앙값을 골라 주므로 흔한 패턴에는 강하지만, 이 규칙을 알고 일부러 만든 입력(“median-of-3 killer”)에는 여전히 O(n²)이 됩니다. 외부 사용자가 입력을 통제할 수 있는 서버 코드라면 랜덤 피벗이나 Introsort처럼 최악을 보장하는 방식이 안전합니다.
문제 2: 병합 정렬 메모리 초과
대용량 배열에서는 병합 정렬의 O(n) 임시 메모리가 부담이 됩니다. 안정성이 필요 없다면 힙 정렬로 바꾸는 것이 가장 간단합니다. 병합 정렬을 유지한다면, 두 구간이 이미 순서대로 놓여 있을 때 병합을 건너뛰는 최적화가 거의 정렬된 입력에서 효과적입니다.
def merge_with_skip(arr, left, mid, right):
# 왼쪽 구간의 최댓값이 오른쪽 구간의 최솟값 이하면 이미 정렬된 상태
if arr[mid] <= arr[mid + 1]:
return
merge_inplace(arr, left, mid, right)진짜 O(1) 공간의 in-place 병합은 구현이 복잡하고 상수 비용이 큽니다. C++의 std::inplace_merge는 임시 버퍼를 할당할 수 있으면 O(n)으로, 할당에 실패하면 버퍼 없이 O(n log n)으로 병합하므로 직접 구현하기보다 이를 쓰는 편이 낫습니다.
문제 3: 안정 정렬 필요
증상: 같은 값의 순서가 바뀜
# 첫 번째 값만 비교하는 불안정 정렬(퀵·힙)
arr = [(1, 'a'), (2, 'b'), (1, 'c')]
# 결과가 [(1, 'c'), (1, 'a'), (2, 'b')]처럼 같은 키의 원래 순서가 바뀔 수 있음해결: 병합 정렬 또는 Python sorted()
arr = [(1, 'a'), (2, 'b'), (1, 'c')]
sorted_arr = sorted(arr, key=lambda x: x[0])
print(sorted_arr)
# [(1, 'a'), (1, 'c'), (2, 'b')] # 순서 유지문제 4: 재귀 깊이 초과 (RecursionError)
증상:
arr = list(range(10000))
quick_sort_inplace(arr, 0, len(arr) - 1)
# RecursionError: maximum recursion depth exceeded해결 1: 재귀 한도 증가
import sys
sys.setrecursionlimit(20000)해결 2: 반복문 변환
def quick_sort_iterative(arr):
stack = [(0, len(arr) - 1)]
while stack:
low, high = stack.pop()
if low < high:
pi = partition(arr, low, high)
stack.append((low, pi - 1))
stack.append((pi + 1, high))재귀 한도를 올리는 것은 증상만 가립니다. 이미 정렬된 1만 개 입력에서 재귀가 1만 단계까지 내려간다는 것은 분할이 O(n²)으로 퇴화했다는 뜻이므로, 한도를 올려서 통과하더라도 느린 것은 그대로입니다. 한도를 너무 크게 올리면 파이썬 인터프리터가 C 스택을 넘어서 RecursionError 대신 세그멘테이션 폴트로 프로세스가 죽을 수도 있습니다. 근본 해결은 랜덤 피벗으로 분할을 균형 있게 만드는 것이고, 반복문으로 바꿀 때는 더 작은 구간을 먼저 처리하도록(큰 구간을 스택에 먼저 넣도록) 하면 스택 크기가 최악에도 O(log n)으로 제한됩니다.
마무리
실무에서는 언어 내장 정렬(sorted(), std::sort(), 안정성이 필요하면 std::stable_sort())을 쓰는 것이 기본입니다. 직접 구현한 원리는 Quick Select나 K-way 병합처럼 정렬의 일부 단계만 필요한 문제, 그리고 메모리·안정성·최악 시간 중 무엇을 포기할지 판단할 때 쓰입니다.
다음 글:
- 기본 정렬: 버블, 선택, 삽입 정렬
- 정렬 문제: 정렬 문제 풀이
- 이진 탐색: 이진 탐색: 경계 조건, lower/upper bound, 결정 문제로 바꾸는 파라메트릭 서치
자주 묻는 질문 (FAQ)
Q. 퀵 정렬이 O(n²)로 느려지는 경우는 어떻게 막나요?
A. 피벗을 항상 첫 원소나 마지막 원소로 고르면 이미 정렬된 입력에서 분할이 한쪽으로 쏠려 O(n²)가 됩니다. 피벗을 무작위로 골라 특정 입력 패턴에 취약하지 않게 만들고, 같은 값이 많은 데이터에서는 피벗보다 작음·같음·큼으로 나누는 3-way 파티션을 쓰면 중복 원소로 인한 퇴화도 줄일 수 있습니다. 분할이 치우치면 재귀도 깊어지므로 Python에서는 RecursionError와도 연결되는 문제입니다.