정렬 알고리즘은 두 값을 비교해서 순서를 정하느냐 아니냐로 크게 갈린다. 비교로 정렬하는 것들은 데이터가 무엇이든 상관없이 쓸 수 있지만, 아무리 잘 만들어도 O(n log n)보다 빠를 수 없다. 이 한계가 왜 생기는지가 정렬 이야기의 뼈대다.
비교 정렬
데이터 사이의 상대적 크기 관계만 이용한다. 숫자든 문자열이든 객체든 둘 중 뭐가 큰가에만 답할 수 있으면 정렬된다.
속도로 다시 두 무리로 나뉜다. O(n²)인 기본 정렬에 버블 정렬, 선택 정렬, 삽입 정렬이 있고, O(n log n)인 고급 정렬에 합병 정렬, 퀵 정렬, 힙 정렬이 있다.
비교하지 않는 정렬
비교를 안 하면 하한을 넘어설 수 있다. 데이터가 가진 특별한 성질을 이용하는 것이다. 값이 정해진 범위의 정수라면 값 자체를 배열 인덱스로 써서 O(n)에 정렬할 수 있고, 계수 정렬과 기수 정렬이 그렇다.
나머지 분류 축
속도 말고도 메모리를 얼마나 더 쓰는가로 제자리 정렬과 내부 정렬, 외부 정렬을 가르고, 같은 값의 순서가 유지되는가로 안정 정렬을 가른다.
n log n 하한의 증명
비교 정렬을 추상적으로 보면 전부 의사 결정 트리다. “a가 b보다 큰가”라는 질문마다 예와 아니오로 갈라지니 이진 트리가 되고, 정렬 과정은 루트에서 리프까지 내려가는 한 경로에 해당한다.
여기서 두 가지를 세어 본다. n개를 정렬한 결과로 가능한 순서는 n!가지이므로 리프가 최소 n!개는 있어야 한다. 그런데 높이가 h인 이진 트리의 리프는 최대 2^h개다. 둘을 합치면 n! ≤ 2^h이고, 양변에 로그를 취하면 h ≥ log(n!)이다. 스털링 근사로 log(n!)은 n log n이니 h ≥ n log n이 된다.
h는 최악의 경우 비교 횟수다. 어떤 비교 정렬도 최악에 n log n번보다 적게 비교할 수 없다. 더 좋은 알고리즘을 못 찾은 게 아니라 존재할 수 없다는 증명이다.
비교를 버리고 하한을 깨는 쪽은 아무 데나 쓸 수 없다는 대가를 치른다. 값의 범위가 작아야 하고, 범위가 크면 공간복잡도에서 막힌다.