Radix Sort

Hermen Hollerith’s card sorting machine for the 1890 US Census

prove is done by

Stable Sort needed for each vertical step

We use

Counting Sort because each step’s sorting value is small

First part of complexity if # of executions of sorting and later part means each execution complexity

We can control as an optimization part to minimize complexity. Increasing means fewer passes and after , the time grows exponentially.

It is convex function. you can find optimal value when the input size and machine architecture is fixed.

If you are lazy, implies which are not best but also not bad.

is usually 32 or 64 so if numbers in the range from 0 to we have . So radix sort runs in

In practice, radix sort is fast for large inputs, as well as simple to code and maintain.

Unlike quicksort, radix sort displays little locality of reference