Sorting algorithms/Radix sort

Sorting algorithms/Radix sort
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log²n) sorts
Shell Sort

O(n²) sorts
Bubble sort | Cocktail sort | Cocktail sort with shifting bounds | Comb sort | Cycle sort | Gnome sort | Insertion sort | Selection sort | Strand sort

other sorts
Bead sort | Bogo sort | Common sorted list | Composite structures sort | Custom comparator sort | Counting sort | Disjoint sublist sort | External sort | Jort sort | Lexicographical sort | Natural sorting | Order by pair comparisons | Order disjoint list items | Order two numerical lists | Object identifier (OID) sort | Pancake sort | Quickselect | Permutation sort | Radix sort | Ranking methods | Remove duplicate elements | Sleep sort | Stooge sort | [Sort letters of a string] | Three variable sort | Topological sort | Tree sort

In this task, the goal is to sort an integer array with the radix sort algorithm. The primary purpose is to complete the characterization of sort algorithms task.

J

Generally, this task should be accomplished in J using /:~. Here we take an approach that's more comparable with the other examples on this page.

keys f/. data evaluates the function f on each group of data at the same position as similar keys. Sorting requires ordered keys. This code uses a J idiom: prepend the keys and matching data. The extra data is removed by behead }..

<lang j>NB. queue implementation of LSB radix sort. radixSort =: 3 : 0 NB. base radixSort data 16 radixSort y

keys =. x #.^:_1 y NB. compute keys length =. {:#{.keys extra =. (x,-length) {. ,. buckets =. i.x for_pass. 0{i.-length do.

 keys =. ,&:>/ (buckets,keys{~"1<pass) <@:}./.extra,keys
 extra =. 1 |. extra

end. x#.keys NB. restore the data )</lang>

Sort 10 small numbers in base 3.

   (,: 3&radixSort) ?@#~10
1 3 8 9 0 0 8 7 1 6
0 0 1 1 3 6 7 8 8 9

Python

The wikipedia article cited in the introduction includes a python implementation of LSB radix sort.