· 개발

퀵 정렬은 언제 O(n²)이 될까: 표준 정렬이 최악을 막는 방법

정렬된 입력, median-of-3 killer, 적대적 비교 함수처럼 퀵 정렬을 이차 시간으로 만드는 경우와 introsort의 깊이 제한, C++·Rust·Go·Java 문서가 보장하는 범위를 정리합니다.

개발알고리즘

퀵 정렬은 평균 O(n log n), 최악 O(n²)이라고 배웁니다. 최악은 어떤 입력에서 나오고, 언어의 기본 정렬에도 그 위험이 있을까요? 퀵 정렬 자체는 지금도 이차 시간이 될 수 있습니다. 여러 표준 라이브러리가 이를 막지만, 그 보장이 명세에 있는지 구현 설명에만 있는지는 언어마다 다릅니다.

분할이 한쪽으로 쏠릴 때

퀵 정렬은 피벗을 골라 나머지를 작은 쪽과 큰 쪽으로 나누고 양쪽을 다시 정렬합니다. 매번 반씩 나뉘면 깊이는 약 log₂ N이고, 깊이마다 N에 비례하는 일을 하므로 전체는 N log N입니다. 분할이 계속 한쪽으로 쏠려 깊이가 N에 비례하면 N²이 됩니다.

쉬운 예는 첫 원소를 피벗으로 쓰는 구현에 정렬된 배열을 넣는 경우입니다. 피벗이 매번 최솟값이라 한쪽이 비고, 비교는 (n−1)+(n−2)+…+1 = n(n−1)/2번 필요합니다. n이 1,000이면 499,500번입니다.

피벗을 잘 골라도 최악은 남는다

첫·가운데·마지막 원소의 중앙값을 쓰는 median-of-3은 정렬된 입력을 잘 나누지만 최악을 없애지는 못합니다. David Musser는 1997년 논문에서 N이 4의 배수일 때 분할이 매번 원소 2개만 떼어 내게 하는 순열, 즉 median-of-3 killer를 제시했습니다. 이 입력에서 median-of-3 퀵 정렬은 Ω(N²)입니다. 당시 HP STL의 sort도 이 방식을 사용했다고 논문은 설명합니다.

무작위 피벗은 나쁜 분할이 이어질 가능성을 낮추지만 최악 한계는 여전히 N²입니다. M. D. McIlroy는 1999년 논문에서 비교 순서를 보며 값을 그때그때 정하는 적대적 비교 함수로 C qsort를 이차 시간에 몰아넣었습니다. 몇 가지 가정 아래 무작위 피벗에도 통하는 방법입니다.

논문의 표에서 Irix 6.4의 median-of-3 qsort는 이 적대자를 상대로 약 0.25n²번 비교했습니다. 이는 1998년 무렵 특정 구현과 특정 적대자를 대상으로 한 측정값입니다. 일반적인 계수도 아니며, 그 구현에서 가능한 궁극적인 최악 사례를 증명한 값도 아닙니다.

깊이에 한도를 두는 introsort

Musser가 제안한 introsort는 median-of-3 퀵 정렬처럼 분할하다가 깊이가 2⌊log₂ N⌋에 이르면 남은 구간을 힙 정렬에 넘깁니다. 힙 정렬은 최악에도 N log N이므로 논문은 introsort의 최악 시간이 Θ(N log N)임을 증명합니다. 대부분의 입력에서는 퀵 정렬과 거의 같게 동작합니다.

힙의 저장 순서는 힙은 정렬된 배열이 아니다에서 다뤘습니다. 논문에 따르면 introsort도 안정 정렬은 아닙니다.

언어 문서가 보장하는 범위

C++. 예전 std::sort의 복잡도는 “평균 대략 N log N번 비교”였고, 최악이 중요하면 stable_sort나 partial_sort를 쓰라는 각주가 있었습니다. 2007년 LWG 713번 이슈는 introsort를 근거로 O(N log N)으로 바꾸고 각주를 지우자고 제안했습니다. 해결안은 2008년 위원회 초안에 반영됐습니다. 현재 작업 초안의 [sort] 조항은 O(N log N)번의 비교와 프로젝션을 요구하지만, 사용할 알고리즘은 정하지 않습니다.

Rust. slice::sort_unstable 문서 본문은 이 정렬이 불안정하고 제자리에서 동작하며 최악 O(n log n)이라고 설명합니다. 퀵 정렬과 힙 정렬을 결합한 ipnsort 기반이라는 내용은 별도의 “Current implementation” 항목에 있습니다.

Go. sort.Sort 문서는 Less와 Swap을 O(n log n)번 호출한다고 명시합니다. pattern-defeating quicksort로 다시 작성했다는 내용은 Go 1.19 릴리스 노트에 있습니다.

Java. Arrays.sort(int[])의 구현 노트는 JDK 8에서 Dual-Pivot Quicksort가 “다른 퀵 정렬을 이차 성능으로 떨어뜨리는 많은 데이터에서” O(n log n) 성능을 낸다고 설명합니다. JDK 25 문구는 이를 “모든 데이터에서”로 표현합니다. 다만 Arrays 클래스 문서는 이런 알고리즘 설명을 명세가 아닌 구현 노트로 보라고 합니다.

직접 구현한다면

직접 구현한다면 깊이 한도와 대체 알고리즘을 함께 두는 편이 안전합니다. 기본 정렬을 사용할 때는 해당 버전의 문서에서 최악 보장이 명세인지, 바뀔 수 있는 구현 노트인지 확인해야 합니다.

문서는 2026년 10월 5일에 확인했습니다.

참고한 논문과 문서

블로그로