Comparison 모델 탈피를 통한 O(n) 시간 복잡도 달성 Radix Sort 분석

Context

기존 Comparison 기반 정렬 알고리즘의 이론적 한계를 극복하기 위한 대안 탐색. 데이터 간 비교 연산 없이 자릿수 기반의 분포 정렬을 통한 성능 최적화 필요성 대두.

Technical Solution

• 0부터 9까지의 10개 Bucket을 활용한 Non-comparison 기반 정렬 구조 설계
• LSD(Least Significant Digit)부터 MSD(Most Significant Digit) 순으로 반복 처리하여 정렬 안정성 확보
• FIFO(First-In, First-Out) 구조의 Queue를 Bucket으로 채택하여 이전 단계의 정렬 순서를 유지하는 Stability 구현
• 각 자릿수별 정렬 완료 후 원본 배열에 Write-back 하여 다음 자릿수 스캔을 위한 상태 전이 수행
• 정렬 대상의 자릿수 제한이라는 제약 조건을 수용하고 시간 복잡도를 O(n)으로 최적화한 설계