비교 정렬의 하한(Comparison sorting lower bound)

병합 정렬⁠(merge sort)⁠은 최악의 경우에도 $n \log_2 n$번을 넘게 비교하지 않고, 힙 정렬⁠(heapsort)⁠은 그 두 배쯤 비교합니다. 둘 다 $n \log n$에 비례합니다. 더 영리한 방법은 없을까요? 두 원소⁠(element)⁠를 비교하는 것만으로 순서를 알아내는 방법이라면 없습니다. 이것은 어떤 특정한 알고리즘⁠(algorithm)⁠이 아니라, 가능한 모든 알고리즘에 대한 주장입니다.

까닭은 세어 보면 나옵니다. 서로 다른 n개를 늘어놓는 순서는 $n!$가지(순열⁠, permutation⁠)이고, 정렬한다는 것은 그중 어느 것인지 알아내는 것입니다. 비교 한 번의 답은 예 아니면 아니오이고, 다음에 무엇을 비교할지는 앞의 답들로 정해집니다. 그러니 k번 비교하면 답의 조합은 많아야 $2^k$가지입니다. 두 순서가 모든 비교에서 같은 답을 받으면 알고리즘은 둘을 구별하지 못하고 둘 중 하나는 틀리게 정렬합니다(비둘기집 원리⁠, pigeonhole principle⁠). 그러니 $2^k \ge n!$, 곧 $k \ge \log_2 n!$입니다. 알고리즘이 할 수 있는 비교를 모두 가지로 그리면 잎⁠(leaf)⁠이 $n!$개 이상인 이진 트리(결정 트리⁠, decision tree⁠)가 되고, 그 높이가 최악의 비교 횟수입니다.

직접 겨뤄 봅시다. 원소 의 순서를 상대가 숨기고 있습니다. 두 원소를 차례로 누르면 어느 쪽이 작은지 답해 줍니다(화살표는 작은 쪽에서 큰 쪽으로). 그런데 이 상대는 심술궂어서, 매번 아직 가능한 순서가 더 많이 남는 쪽으로 대답합니다. 다시 하기

오른쪽 막대가 증명 그 자체입니다. 어떤 쌍을 물어도 상대가 많은 쪽을 남기므로 남은 순서의 수는 한 번에 많아야 절반으로 줄고(막대가 1씩 낮아지는 회색 점선보다 빨리 내려갈 수 없고), 1이 되려면 적어도 $\lceil \log_2 n! \rceil$번이 필요합니다. 반대로 매번 남은 순서를 반에 가깝게 가르는 쌍을 고르면, 작은 n에서는 이 한계에 닿거나 가깝게 끝낼 수 있습니다. 다섯 개는 7번($\lceil \log_2 120 \rceil = 7$)이면 정렬할 수 있고, 포드와 존슨의 병합 삽입⁠(merge insertion)⁠ 정렬(1959)이 그런 방법입니다. 그러나 이 한계에 늘 닿는 것은 아닙니다. 열두 개는 $\lceil \log_2 12! \rceil = 29$번이 아니라 30번이 필요하다는 것이 컴퓨터 탐색으로 밝혀졌습니다.

스털링 공식⁠(Stirling's formula)⁠에 따르면 $\log_2 n! = n \log_2 n - n \log_2 e + O(\log n)$이니 이 하한⁠(lower bound)⁠은 $\Omega(n \log n)$입니다. 병합 정렬의 최악은 첫째 항 $n \log_2 n$까지 이 하한과 같으니, 점근적으로 최선입니다. $n =$ 이면 하한은 번, 병합 정렬의 최악은 번, $n \log_2 n$은 입니다. 모든 순서가 똑같이 그럴듯하다고 보고 평균⁠(mean)⁠을 따져도 결론은 같습니다. 잎이 $n!$개인 이진 트리⁠(binary tree)⁠에서는 잎까지의 평균 깊이도 $\log_2 n!$보다 작을 수 없기 때문입니다.

이어지는 곳. 이것은 엔트로피⁠(entropy)⁠로 본 한계입니다. 똑같이 그럴듯한 $n!$가지 중 하나를 가려내려면 $\log_2 n!$비트의 정보가 필요한데, 한 번의 비교는 많아야 1비트를 줍니다. 이진 탐색⁠(binary search)⁠이 최악의 경우 $\log_2 n$번보다 빠를 수 없는 것도, 원래 자료를 한 비트도 잃지 않고 되살릴 수 있는 무손실 압축⁠(lossless compression)⁠은 평균적으로 엔트로피보다 짧아질 수 없다는 섀넌의 원천 부호화 정리⁠(source coding theorem)⁠도 같은 셈입니다. 자료를 예/아니오 질문으로 나누어 예측하는 기계 학습⁠(machine learning)⁠의 결정 트리도 같은 모양의 나무이고, 질문마다 엔트로피를 가장 많이 줄이는 것을 욕심껏 고릅니다. 비교 말고 다른 연산을 쓰면 한계를 넘을 수 있습니다. 수를 자릿수별로 칸에 나눠 담는 기수 정렬⁠(radix sort)⁠은 자릿수가 정해져 있으면 $O(n)$입니다.