Merge sort는 항상 O(n log n)을 보장하고 stable하지만 O(n) 추가 메모리가 필요합니다. Quick sort는 평균 O(n log n)이고 in-place로 동작하지만, pivot 선택이 나쁘면 O(n²)로 악화됩니다. 실제 표준 라이브러리는 두 방식을 혼합한 introsort 계열을 씁니다.
두 알고리즘 모두 분할 정복(divide and conquer)이지만, 정렬이라는 실제 일이 일어나는 시점이 다릅니다. Merge sort는 분할은 기계적으로 절반씩 자르기만 하고, 합칠 때(merge) 두 정렬된 배열을 비교하며 정렬합니다. Quick sort는 나눌 때(partition) pivot 기준으로 원소를 재배치하며 정렬하고, 합치는 단계는 아예 없습니다.
이 구조 차이가 두 알고리즘의 모든 특성 차이를 만듭니다. Merge sort는 병합 결과를 담을 임시 배열이 필요해 O(n) 추가 공간을 쓰고, 병합 시 왼쪽 배열을 먼저 쓰기 때문에 같은 값의 순서가 유지되어 stable합니다. Quick sort는 제자리 교환만 하므로 추가 공간이 없지만, 분할이 얼마나 균등한지가 pivot 운에 달려 있어 최악 O(n²)이 생깁니다. Merge sort의 분할은 항상 정확히 절반이라 최악이 없습니다.
꼬리질문
조금 더 깊게 물어본다면
답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.
Quick sort 최악 케이스를 어떻게 줄이나요?
pivot을 무작위로 선택하거나 세 값의 중간값을 pivot으로 쓰는 median-of-three를 적용합니다. C++ STL의 std::sort는 재귀 깊이가 커지면 heap sort로 전환하는 introsort를 씁니다.
최악 케이스가 이론적 우려가 아닌 이유는, O(n²)를 유발하는 입력이 실무에서 흔하기 때문입니다. 첫 번째 원소를 pivot으로 고르는 순진한 구현에 이미 정렬된 배열이 들어오면, 매번 분할이 1 대 (n-1)로 쪼개져 정확히 O(n²)가 됩니다. 이미 정렬됐거나 거의 정렬된 데이터는 실무에서 가장 흔한 입력 중 하나입니다.
무작위 pivot은 특정 입력이 항상 최악이 되는 상황을 없앱니다. 어떤 입력이 오든 최악이 될 확률이 무시할 수준으로 낮아집니다. median-of-three는 맨 앞, 중간, 맨 뒤 세 값의 중간값을 pivot으로 써서, 정렬된 입력에서도 중간값 근처가 선택되게 합니다. 다만 두 방법 모두 확률을 낮출 뿐 최악을 제거하지는 못해서, 보장이 필요하면 introsort처럼 다른 알고리즘으로의 전환이 필요합니다.
C++ std::sort는 어떤 알고리즘을 쓰나요?
introsort입니다. quick sort로 시작해 재귀 깊이가 log n을 넘으면 heap sort로 전환하고, 원소 수가 적으면 insertion sort를 씁니다. 이렇게 세 알고리즘의 장점을 결합해 최악 O(n log n)을 보장합니다.
세 알고리즘의 역할 분담이 명확합니다. Quick sort는 평균적으로 가장 빠르니 기본으로 쓰고, 재귀 깊이가 비정상적으로 깊어지는 것은 분할이 계속 한쪽으로 쏠린다는 신호이므로 그 시점에 heap sort로 갈아탑니다. Heap sort는 캐시 지역성이 나빠 평균은 quick sort보다 느리지만, 어떤 입력에도 O(n log n)과 in-place를 보장하니 안전망으로 적합합니다.
원소가 적을 때(구현마다 다르지만 대략 16개 안팎) insertion sort로 바꾸는 이유는 상수 비용입니다. 재귀 호출과 pivot 선택의 오버헤드가 작은 배열에서는 원소를 하나씩 밀어 넣는 단순 반복보다 비쌉니다. insertion sort는 거의 정렬된 짧은 구간에서 비교 몇 번으로 끝나기 때문에, quick sort가 대충 정렬해 놓은 작은 구간의 마무리로 잘 맞습니다.
Stable sort가 필요할 때는?
Merge sort나 C++의 std::stable_sort를 씁니다. Quick sort는 기본적으로 stable하지 않아 같은 값 원소의 순서를 보장하지 않습니다.
stable이 실제로 필요한 대표 상황은 다중 기준 정렬입니다. 이름순으로 정렬된 사원 명단을 부서순으로 다시 정렬할 때, stable sort라면 같은 부서 안에서 이름순이 그대로 유지됩니다. unstable sort는 같은 부서 원소들의 상대 순서를 뒤섞을 수 있어, 기준을 하나씩 연달아 적용하는 방식이 성립하지 않습니다.
Python의 sorted()와 Java의 Collections.sort()가 쓰는 Timsort도 merge sort 계열이라 stable합니다. 실제 데이터에 이미 정렬된 구간(run)이 많다는 관찰에서 출발해, 기존 run을 찾아 병합하는 방식으로 정렬된 입력에서는 O(n)에 가깝게 동작합니다. C++ std::stable_sort는 추가 메모리를 확보할 수 있으면 O(n log n), 확보하지 못하면 in-place 병합으로 O(n log² n)이 됩니다. 안정성에는 메모리든 시간이든 비용이 따릅니다.
외부 정렬에 merge sort가 유리한 이유는?
디스크에 있는 데이터를 정렬할 때 순차 읽기 패턴이 중요합니다. Merge sort는 데이터를 순차적으로 읽어 병합하는 구조라 디스크 I/O에 적합합니다. Quick sort의 랜덤 접근 패턴은 디스크에서 seek 비용이 커집니다.
외부 정렬(external sort)은 메모리에 다 안 들어가는 데이터를 정렬하는 기법입니다. 실제 동작은 두 단계입니다. 먼저 메모리 크기만큼 데이터를 읽어 내부에서 정렬한 뒤 디스크에 정렬된 조각(run)으로 저장하는 것을 반복하고, 그다음 여러 run을 동시에 열어 각 run의 맨 앞 값 중 최솟값을 뽑아 쓰는 k-way merge로 합칩니다. 두 단계 모두 디스크를 처음부터 끝까지 순차로만 읽고 씁니다.
순차 접근이 중요한 이유는 HDD의 seek(헤드 이동) 비용이 밀리초 단위로, 순차 읽기 대비 수백 배 이상 느리기 때문입니다. Quick sort의 partition은 배열 양 끝에서 안쪽으로 접근하고 재귀마다 위치가 흩어져 디스크에서는 seek이 반복됩니다. 데이터베이스가 메모리를 초과하는 ORDER BY를 처리할 때 디스크로 흘려보내며(spill) external merge sort를 쓰는 것이 대표적인 예입니다.
O(n log n)보다 빠른 정렬 알고리즘이 있나요?
비교 기반 정렬은 O(n log n)이 하한이지만, 비교를 아예 안 하는 정렬은 더 빠를 수 있습니다. Counting sort와 Radix sort가 대표적입니다.
Counting sort는 값의 범위가 작을 때 씁니다. 각 값이 몇 번 등장하는지 세어 누적합으로 위치를 결정합니다. 시간복잡도는 O(n + k)로, k가 값의 범위입니다. 정수 배열에서 값 범위가 크지 않으면 O(n)에 가깝습니다. 실수나 범위가 넓은 정수에는 쓸 수 없습니다.
Radix sort는 자릿수별로 반복 정렬합니다. 각 자릿수에 counting sort를 적용해 전체 O(d·n)이 됩니다. d는 최대 자릿수입니다. 32비트 정수는 d가 고정이라 O(n)으로 볼 수 있습니다. 범용 정렬보다 빠르지만 정수나 고정 길이 문자열처럼 자릿수 개념이 있는 데이터에만 씁니다.
비교 기반 정렬은 왜 O(n log n)이 하한일까요? n개 원소를 정렬하면 n! 가지 경우의 수가 있습니다. 비교 한 번은 이 경우의 수를 최대 절반으로 줄입니다. 모든 경우를 구분하려면 최소 log₂(n!) 번의 비교가 필요하고, Stirling 근사에 의해 log₂(n!) ≈ n log n 이 됩니다. 이 하한은 어떤 비교 기반 알고리즘으로도 깰 수 없습니다.
세계에서 가장 빠른 정렬 알고리즘의 lower bound는?
비교 기반 정렬이라면 O(n log n)입니다. 어떤 알고리즘도 비교만으로는 이보다 적은 횟수로 n개를 정렬할 수 없다는 것이 증명되어 있습니다.
증명은 결정 트리(decision tree)로 합니다. 비교 기반 정렬을 이진 트리로 표현하면 각 내부 노드는 비교 결과(크다/작다), 각 리프는 정렬된 순서 하나입니다. n개 원소는 n!가지 순서가 있으므로 리프가 최소 n!개 필요합니다. 높이가 h인 이진 트리의 리프는 최대 2ʰ개이므로 2ʰ ≥ n!, h ≥ log₂(n!) ≈ n log n 이 됩니다. 이 h가 최악 비교 횟수의 하한입니다.
비교를 안 하는 알고리즘(counting sort, radix sort)은 이 제약에서 자유롭습니다. 데이터의 추가 속성(값 범위, 자릿수)을 활용하기 때문입니다.
부가 설명
Merge sort는 배열을 절반으로 나누고 각각을 정렬한 뒤 병합합니다. 병합 과정에서 임시 배열이 필요하므로 O(n) 추가 공간을 씁니다. 같은 값의 원소 순서가 유지되어 stable합니다. 최선, 평균, 최악 모두 O(n log n)입니다.
Quick sort는 pivot을 골라 작은 값은 왼쪽, 큰 값은 오른쪽으로 분리한 뒤 재귀합니다. 제자리에서 동작해 추가 메모리가 거의 없습니다. 평균은 O(n log n)이지만 pivot이 항상 최솟값이나 최댓값으로 선택되면 O(n²)입니다. Randomized quick sort나 median-of-three로 최악 케이스를 완화합니다.
실제로는 cache locality 덕분에 quick sort가 merge sort보다 빠른 경우가 많습니다. 메모리에 연속 배치된 원소를 제자리에서 교환하므로 캐시 적중률이 높습니다. Merge sort는 외부 정렬이나 linked list 정렬처럼 랜덤 접근 비용이 큰 상황에 유리합니다.
한 줄 정리
Merge sort는 안정성과 최악 보장, quick sort는 실제 속도와 공간 효율을 우선할 때 선택하며, 표준 라이브러리는 두 방식을 조합합니다.