정의

기수 정렬은 숫자를 "자릿수" 단위로 쪼개어, 낮은 자리부터 차례대로 0~9번 버킷에 나눠 담았다가 다시 모으는 일을 반복하는 정렬 알고리즘입니다. 두 수의 크기를 직접 비교하지 않는 것이 특징입니다.

핵심 특성

• ✓비교를 하지 않습니다: 대소 비교 대신 "자릿수 숫자(0~9)"를 그대로 버킷 번호로 사용합니다.
• ✓안정 정렬(Stable): 같은 자릿수를 가진 값은 들어온 순서를 그대로 유지합니다. 이 성질 덕분에 낮은 자리부터 처리해도 결과가 망가지지 않습니다.
• ✓자릿수(d)만큼만 반복: 데이터 개수 n과 거의 무관하게, 가장 큰 수의 자릿수 d번만 패스를 돕니다.

시간 복잡도