Radix-Sort

Antagelse: Listen består av tall som har $d$ siffer.

Sorts different numbers in the correct order. See picture below Requires a Stable matching algorithms

Runtime

Since we use Counting Sort:

$$\begin{array}{rl}& \\ Count-Sort& :T(n)=O(n+k)\\ & \\ Radix-Sort& :T(n)=O(d(n+k))\end{array}$$

Which means if d and k are constants we achieve linear time!