왜 “비교하지 않는 정렬”이 따로 필요한가

06~08편에서 다룬 선택·삽입·버블·퀵·합병·히프 정렬은 모두 두 원소의 크기를 직접 비교해서 순서를 정한다는 공통점이 있다. “이 값이 저 값보다 큰가 작은가”라는 질문을 반복해서 던지고, 그 답에 따라 원소를 옮기는 방식이다. 그런데 이런 비교 기반 정렬(comparison-based sort)에는 이론적인 한계가 있다. 아무리 영리하게 비교 순서를 짜도, 정렬을 완료하려면 최악의 경우 원소 개수 $n$에 대해 $O(n \log n)$번의 비교가 필요하다는 사실이 수학적으로 증명되어 있다(이 편의 마지막 절에서 직접 증명한다).

그렇다면 “비교를 아예 하지 않는” 정렬을 만들면 이 하한을 피해갈 수 있지 않을까? 계수 정렬(counting sort)과 기수 정렬(radix sort)이 바로 그 답이다. 두 정렬은 원소끼리 크기를 비교하는 대신, 값 자체를 배열의 인덱스로 직접 사용해서 순서를 정한다. 독학사 4단계 시험에서는 “왜 기수 정렬이 O(n log n) 하한을 넘어설 수 있는가”를 묻는 문항이 자주 나오므로, 단순히 절차를 외우는 것을 넘어 왜 그것이 가능한지를 이해해야 한다.

쉽게 말하면: 비교 정렬은 “누가 더 큰지” 물어보며 순서를 찾아내고, 계수·기수 정렬은 값 자체를 “몇 번째 칸에 넣을지”를 계산하는 주소로 써서 비교 없이 바로 제자리를 찾는다.

계수 정렬 — 값을 세어서 위치를 계산한다

계수 정렬(counting sort)은 정렬할 값들이 $0$부터 $k$까지의 정수 범위 안에 있다는 사실을 이용한다. 아이디어는 “각 값이 몇 개씩 있는지 세어 두면, 그 개수만으로 정렬된 배열에서 각 값이 차지할 위치를 계산할 수 있다”는 것이다. 이 편에서는 원소 개수 $n = 7$, 값의 범위 $k = 8$(값은 0부터 8까지 가능)인 예시 배열로 전 과정을 추적한다.

이 과정 전체에서 원소끼리 크기를 비교하는 연산은 단 한 번도 없었다. 값을 count 배열의 인덱스로 직접 사용해서 개수를 세고, 그 개수의 누적합으로 최종 위치를 바로 계산했을 뿐이다.

계수 정렬의 복잡도

계수 정렬은 세 단계 각각이 걸리는 시간을 더하면 전체 시간이 나온다.

• $n$: 정렬할 원소의 개수
• $k$: 값이 가질 수 있는 범위(0부터 $k$까지이므로 $k+1$가지 값)

이 복잡도는 최선·평균·최악이 모두 동일하게 $O(n+k)$ 다. 값을 비교하지 않으므로 입력의 배열 순서(이미 정렬되어 있는지, 역순인지)가 시간에 전혀 영향을 주지 않기 때문이다. 다만 이 성능은 $k$가 $n$에 비해 지나치게 크지 않을 때만 의미가 있다. 예를 들어 $n = 100$인데 값의 범위가 $k = 1{,}000{,}000$이라면, count 배열을 만들고 훑는 데만 100만 번 가까운 작업이 필요해 오히려 $O(n \log n)$ 비교 정렬보다 느려진다.

자주 틀리는 점: “계수 정렬은 항상 O(n)이다”라고 단순화하면 안 된다. 정확한 복잡도는 $O(n+k)$이며, $k$가 $n$보다 훨씬 크면 실제로는 매우 느려질 수 있다. 계수 정렬은 값의 범위가 원소 개수와 비슷한 수준으로 제한되어 있을 때만 실용적이다.

기수 정렬 — 계수 정렬을 자릿수마다 반복한다

기수 정렬(radix sort)은 값의 범위 $k$가 너무 커서 계수 정렬을 통째로 적용하기 어려운 경우(예: 세 자리 이상의 정수)에, 값을 자릿수(digit) 단위로 쪼개서 각 자릿수에 대해 계수 정렬을 반복 적용하는 방식이다. 자릿수 하나의 범위는 10진수 기준 0~9뿐이므로, 매 패스마다 계수 정렬의 $k$가 항상 9로 작게 고정된다는 것이 핵심 아이디어다.

이 편에서는 최하위 자릿수부터(Least Significant Digit, LSD) 처리하는 방식으로, 세 자리 정수 7개를 정렬하는 전 과정을 추적한다.

세 번의 자릿수 패스를 거치자 329, 355, 436, 457, 657, 720, 839로 완전히 정렬되었다. 왜 최하위 자릿수부터 처리해야 하는가가 이 알고리즘의 핵심 함정이다. 만약 반대로 최상위 자릿수(100의 자리)부터 처리한다면, 100의 자리가 같은 원소들(예: 329와 355, 둘 다 100의 자리가 3) 사이의 순서를 그 뒤의 10의 자리·1의 자리로 다시 정해 줘야 하는데, 이를 올바르게 처리하려면 훨씬 복잡한 재귀적 절차가 필요하다. LSD 방식은 “이미 정렬된 하위 자릿수 순서 위에 상위 자릿수 정렬을 안정적으로 덧씌운다”는 전략이라, 매 패스가 반드시 안정 정렬이기만 하면 최종 결과가 자동으로 올바른 전체 순서가 된다는 점이 이 방식의 우아함이다.

자주 틀리는 점: 기수 정렬의 각 자릿수 패스에 안정적이지 않은 정렬(예: 퀵 정렬)을 쓰면 안 된다. 값이 같은 자릿수를 가진 원소들의 상대적 순서가 패스마다 뒤바뀌면, 이전 패스에서 애써 맞춰 둔 하위 자릿수 순서가 깨져 최종 결과가 틀린 정렬이 되어버린다.

기수 정렬의 복잡도

자릿수(패스) 개수를 $d$, 원소 개수를 $n$, 자릿수 하나가 가질 수 있는 값의 개수(10진수라면 $k=10$)라 하면, 각 패스는 계수 정렬 $O(n+k)$가 걸리고 이를 $d$번 반복하므로 다음과 같다.

위 예시에서는 $n=7$, $d=3$(자릿수 3개), $k=10$이므로 $O(3 \times (7+10)) = O(51)$ 수준의 작업이 필요했다. 만약 $d$와 $k$를 상수로 볼 수 있는 상황(예: “32비트 정수만 다룬다”처럼 자릿수 범위가 고정된 경우)이라면, 기수 정렬의 시간 복잡도는 사실상 $O(n)$에 가까워진다. 이는 다음 절에서 증명할 비교 정렬의 이론적 하한 $\Omega(n \log n)$보다 빠른 것으로, “비교하지 않는 정렬만이 도달할 수 있는 영역”이다.

비교 기반 정렬은 왜 O(n log n)보다 빨라질 수 없는가

이제 이 편의 핵심 질문에 답한다. 어떤 비교 기반 정렬 알고리즘도 최악의 경우 $\Omega(n \log n)$번의 비교 없이는 정렬을 끝낼 수 없다는 사실을 증명한다.

정렬을 결정 트리로 표현하기

원소가 $n$개인 배열을 정렬한다는 것은, $n!$가지의 가능한 순서(순열, permutation) 중 정확히 하나를 찾아내는 일이다. 비교 기반 정렬 알고리즘이 “두 원소를 비교한다”는 행동을 한 번 할 때마다, 그 결과는 “크다” 또는 “작다”(또는 “같다”) 둘 중 하나이므로, 알고리즘 전체의 동작을 이진 트리(binary tree) 하나로 그릴 수 있다. 트리의 각 내부 노드는 “이 두 원소 중 어느 것이 큰가”라는 비교 하나를 나타내고, 각 리프(leaf) 노드는 그 비교들의 결과로 확정된 하나의 최종 순서를 나타낸다. 이런 트리를 결정 트리(decision tree)라 부른다.

원소가 서로 다른 값으로만 이루어져 있다면, 가능한 최종 순서는 정확히 $n!$가지이므로, 이 결정 트리는 반드시 최소 $n!$개의 리프를 가져야 한다. 어떤 순열도 결과로 나올 수 있어야 하는데, 만약 리프가 $n!$개보다 적다면 어떤 두 순열이 같은 리프로 표현되어 알고리즘이 그 둘을 구분하지 못한다는 뜻이 되어 모순이다.

트리 높이와 최악 비교 횟수의 관계

이진 트리에서 높이(루트에서 가장 먼 리프까지의 비교 횟수)가 $h$면, 리프의 개수는 최대 $2^h$개다(각 내부 노드가 자식을 최대 2개만 가지므로). 이 트리가 $n!$개 이상의 리프를 가지려면 다음이 성립해야 한다.

양변에 로그를 취하면 다음과 같다.

• $h$: 결정 트리의 높이. 즉 이 알고리즘이 최악의 경우 수행해야 하는 비교 횟수
• $n!$: 원소 $n$개로 만들 수 있는 전체 순열의 개수
• $\log_2(n!)$: $n!$을 밑이 2인 로그로 취한 값

log2(n!)가 왜 n log n 수준인가

$\log_2(n!)$을 직접 계산하기 쉽게 풀어보면, $n! = n \times (n-1) \times \cdots \times 2 \times 1$이므로 다음과 같다.

이 합의 뒤쪽 절반(즉 $n/2$번째 항부터 $n$번째 항까지, 항이 $n/2$개)은 모두 $\log_2(n/2)$ 이상이므로, 전체 합은 최소한 다음 크기 이상이다.

우변을 정리하면 $\frac{n}{2}\log_2 n - \frac{n}{2}$가 되어, $n$이 커질수록 이 값은 $n \log_2 n$에 비례해서 커진다. 따라서 다음 결론에 도달한다.

즉 어떤 비교 기반 정렬 알고리즘도, 아무리 영리하게 설계해도, 최악의 경우 $\Omega(n \log n)$번의 비교를 피할 수 없다. 07~08편에서 본 합병 정렬·히프 정렬이 최선·평균·최악 모두 $O(n \log n)$을 달성한 것은 우연이 아니라, 이 이론적 하한에 정확히 도달한 최적의 비교 정렬이라는 뜻이다.

왜 계수·기수 정렬은 이 하한을 벗어날 수 있는가

이 결정 트리 논증은 “두 원소를 비교해서 순서를 정한다”는 방식에만 적용된다. 계수 정렬과 기수 정렬은 원소끼리 비교하는 연산 자체가 없고, 값을 배열의 인덱스로 직접 변환해 위치를 계산한다. 결정 트리 모델 자체가 이 알고리즘들의 동작을 표현하지 못하므로, $\Omega(n \log n)$ 하한이 애초에 적용되지 않는다. 대신 이 알고리즘들은 값의 범위 $k$에 의존하는 $O(n+k)$ 또는 $O(d(n+k))$라는, 하한과는 다른 차원의 대가를 치른다.

자주 틀리는 점: “기수 정렬이 항상 더 빠르므로 비교 정렬은 쓸모없다”고 단정하면 안 된다. 기수 정렬은 값이 정수(또는 고정 자릿수 키)로 제한될 때만 적용할 수 있고, 임의의 부동소수점·문자열·객체를 사용자 정의 기준으로 정렬해야 하는 일반적인 상황에서는 여전히 비교 기반 정렬이 필요하다. 또한 $k$나 $d$가 $n$에 비해 매우 크면 기수 정렬이 오히려 더 느려질 수 있다.

자주 틀리는 점

• 계수 정렬의 복잡도를 무조건 $O(n)$으로 외우는 실수: 정확한 복잡도는 $O(n+k)$이며, $k$가 크면 실용적이지 않다.
• 기수 정렬을 최상위 자릿수부터 처리해도 된다고 착각하는 실수: LSD 방식이 아니라 최상위 자릿수(Most Significant Digit, MSD)부터 처리하려면, 같은 자릿수를 가진 그룹을 재귀적으로 다시 나누는 훨씬 복잡한 절차가 필요하다. 독학사 시험에서 “기수 정렬”이라고만 하면 보통 더 간단한 LSD 방식을 가리킨다.
• 기수 정렬의 자릿수 패스에 안정적이지 않은 정렬을 써도 된다고 착각하는 실수: 각 패스가 안정 정렬이 아니면 이전 패스에서 맞춘 순서가 깨져 최종 결과가 틀린다.
• 결정 트리의 리프 개수를 $n$개로 착각하는 실수: 리프 개수는 원소 개수 $n$이 아니라, 가능한 전체 순열의 개수인 $n!$이다.
• $\Omega(n \log n)$ 하한이 모든 정렬에 적용된다고 착각하는 실수: 이 하한은 비교 기반 정렬에만 적용되며, 계수·기수 정렬처럼 비교를 하지 않는 알고리즘에는 적용되지 않는다.

핵심 정리

• 계수 정렬은 값별 개수를 센 뒤 누적합으로 최종 위치를 계산해 $O(n+k)$에 정렬하며, 원소끼리 비교하는 연산이 전혀 없다.
• 기수 정렬은 값의 범위가 너무 커서 계수 정렬을 통째로 쓰기 어려울 때, 자릿수 단위로 쪼개 최하위 자릿수부터 안정적인 계수 정렬을 반복 적용해 $O(d(n+k))$에 정렬한다.
• 비교 기반 정렬은 결정 트리 논증에 따라 최악의 경우 $\Omega(n \log n)$번의 비교를 피할 수 없으며, 합병·히프 정렬은 이 하한에 정확히 도달한 최적 정렬이다.
• 계수·기수 정렬은 비교를 하지 않기 때문에 이 하한의 적용 대상이 아니지만, 대신 값의 범위 $k$(또는 자릿수 $d$)에 비례하는 비용을 치르므로 정수 등 범위가 제한된 키에만 실용적이다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제  — 알고리즘 과목 출제기준·평가영역 확인용 공식 안내.
• GeeksforGeeks — Counting Sort  — 계수 정렬의 누적합 기반 배치 절차와 복잡도 설명 참고 자료.