Radix Sort

Radix Sort

• 비교기반 정렬이 아님. 일종의 비대칭 무기
• 10진법이 아니라 K진법을 쓰게 하면, int32_t 범위 내에서 오히려 기존 Sort보다 앞서는 성능을 보임
• k진법에서 각 자리수의 cnt를 저장한 뒤 재배치하도록 하면, 메모리 공간도 $O(N)$ 으로 구현가능

Time Complexity

• Worst: $O(N + K)$