카운팅 정렬(Counting Sort)이 비교 기반 정렬보다 빠를 수 있는 이유는?

해설

카운팅 정렬은 값의 범위(k)가 작을 때 원소 간 비교 없이 각 값의 등장 횟수를 세어 정렬합니다. 시간 복잡도가 O(n+k)로 비교 기반 정렬의 하한인 O(n log n)보다 빠를 수 있지만, 값의 범위가 크면 메모리와 시간이 비효율적입니다.