= Radix sort
{title2=$T(n,d,R)=O(d(n+R))$}
{wiki}
<Radix sort> sorts encoded <sort keys> a digit at a time. Its least-significant-digit version uses <stable sorting> on each successive digit, often by <counting sort>. For $d$ digits with $R$ possible values each, it takes $O(d(n+R))$ <time complexity> in <Big O notation>, assuming constant-cost digit extraction and indexing. <Stable sorting> retains the ordering established by earlier digits when a later digit ties. Both digit access and the direct indexing in <counting sort> lie outside the <comparison sort> model, so these bounds do not contradict the <comparison sorting lower bound>.<Open Data Structures: An Introduction by Pat Morin/11.2 Counting Sort and Radix Sort>[Theorem 11.8]{ref}
Back to article page
