Motivation

기수 정렬(Radix Sort)은 두 숫자를 직접 비교하지 않습니다. 안정적인 보조 정렬(stable helper sort)을 사용하여 한 번에 한 자리씩 그룹화하며, 이를 통해 비교 정렬이 넘을 수 없는 O(n log n)의 벽을 깰 수 있습니다.

왜 기수 정렬을 배워야 할까요?

• 선형에 가까운 시간 복잡도: d가 자릿수이고 k가 기수(여기서는 10)일 때 O(d * (n + k))의 속도로 실행됩니다. 자릿수가 제한된 숫자의 경우, 이는 사실상 O(n)입니다.
• 안정성(Stable): 동일한 값들이 상대적인 순서를 유지하며, 이것이 바로 자릿수별 정렬 단계가 올바르게 결합될 수 있게 해주는 핵심입니다.
• 색다른 접근 방식: 정렬이 반드시 비교를 의미할 필요는 없음을 보여주며, 이는 큰 정수나 고정 폭 키(fixed-width keys)를 다룰 때 중요한 통찰력을 제공합니다.

트레이드오프: 자릿수로 나눌 수 있는 키(여기서는 음수가 아닌 정수)가 필요하며, 버킷을 위한 추가 메모리가 필요합니다.