Editing Radix sort (section)

== Examples ==

=== Least significant digit ===
Input list:
:'''[170, 45, 75, 90, 2, 802, 2, 66]'''

Starting from the rightmost (last) digit, sort the numbers based on that digit:

:'''[{17<u>0</u>, 9<u>0</u>}, {<u>2</u>, 80<u>2</u>, <u>2</u>}, {4<u>5</u>, 7<u>5</u>}, {6<u>6</u>}]'''

Sorting by the next left digit:

:'''[{''<u>0</u>''2, 8<u>0</u>2, ''<u>0</u>''2}, {<u>4</u>5}, {<u>6</u>6}, {1<u>7</u>0, <u>7</u>5}, {<u>9</u>0}]'''

:<small>Notice that an implicit digit ''0'' is prepended for the two 2s so that 802 maintains its position between them.</small>

And finally by the leftmost digit:

:'''[{''<u>0</u>0''2, ''<u>0</u>0''2, ''<u>0</u>''45, ''<u>0</u>''66, ''<u>0</u>''75, ''<u>0</u>''90}, {<u>1</u>70}, {<u>8</u>02}]'''

:<small>Notice that a ''0'' is prepended to all of the 1- or 2-digit numbers.</small>

Each step requires just a single pass over the data, since each item can be placed in its bucket without comparison with any other element.

Some radix sort implementations allocate space for buckets by first counting the number of keys that belong in each bucket before moving keys into those buckets. The number of times that each digit occurs is stored in an [[Array data type|array]].

Although it is always possible to pre-determine the bucket boundaries using counts, some implementations opt to use dynamic memory allocation instead.

=== Most significant digit, forward recursive  ===

Input list, fixed width numeric strings with leading zeros:
:'''[170, 045, 075, 025, 002, 024, 802, 066]'''

First digit, with brackets indicating buckets:
:'''[{<u>0</u>45, <u>0</u>75, <u>0</u>25, <u>0</u>02, <u>0</u>24, <u>0</u>66}, {<u>1</u>70}, {<u>8</u>02}]'''

:<small>Notice that 170 and 802 are already complete because they are all that remain in their buckets, so no further recursion is needed</small>

Next digit:
:'''[{ {0<u>0</u>2}, {0<u>2</u>5, 0<u>2</u>4}, {0<u>4</u>5}, {0<u>6</u>6}, {0<u>7</u>5} }, 170, 802]'''

Final digit:
:'''[ 002, { {02<u>4</u>}, {02<u>5</u>} }, 045, 066, 075 , 170, 802]'''

All that remains is concatenation:
:'''[002, 024, 025, 045, 066, 075, 170, 802]'''