비교 정렬은 키 사이의 비교 결과를 이용해 순서를 결정하는 정렬 알고리즘의 부류이다. 병합 정렬과 퀵 정렬 등이 속한다.
원리
서로 다른 n개 원소에는 n!가지 입력 순서가 있다. 비교 의사결정 트리로 이 경우들을 구별해야 하므로 일반적인 비교 정렬에는 최악 Ω(n log n)의 비교 하한이 있다.
예시
정수뿐 아니라 사용자 정의 객체도 일관된 비교 함수가 있으면 비교 정렬로 처리할 수 있다.
주의할 점
이 하한은 비교만으로 순서를 알아내는 모형의 결과다. 제한된 정수 범위를 활용하는 계수 정렬에 그대로 적용하지 않는다.