Radix Sort

Radix Sort is a sorting algorithm that works without any comparison. Instead it works by creating buckets and distributing the elements into them with an assigned key.

Radix Sort can be implemented in two ways:

• Least Significant Digit Sort
• Most Significant Digit Sort

---

Complexity

The complexity values for the Radix Sort are:

Aspect	Complexity
Time	$O(d(n+b))$
Space	$O(n+b)$

Where:

• $d$ is the maximum number of digits
• $b$ is the base of the number system used
• $n$ is the length of the list to be sorted