동일한 값이 빈번하게 등장한다는건 입력값의 dynamic range 가 협소하거나,

범위 내의 표현 빈도가 편중되었다는거잖아.

dynamic range 가 협소하다면 counter sort 를 쓰는게 유리하고,

sparse 하다면 먼저 서수화한 다음 counter sort 계열을 쓰는게 유리하고 말야.


counter sort 특성상 표현범위가 협소하거나 데이타가 무진장 많아야 유리하니까,

2만건 이하로 넓은 표현범위를 가질때 quick sort 같은걸 쓰는거고

건수가 무쟈게 많으면 카운터 소트 + 버킷 정렬 ( 이를테면 radix sort ) 처럼

swap 이 빈번하게 일어나는 항목들끼리 클러스터링 해줘야 유리한거지.


다른 아이가 말했듯, 별도 처리를 위한 코드가 늘어나는게 code cache 에 상당히 안좋다.

간단한게 아름답고 좋은것이여~