Python DSALesson 110Free preview

Radix Sort

This lesson is part of Python · All levels

Summary

This lesson explains Radix Sort, a sequencing algorithm that works digit by digit instead of comparing the entire value. The sequencing is repeated starting from the lowest digit (LSD) or highest digit (MSD) with the help of a stable algorithm such as counting sort. Radix sort includes non-comparison sort and can reach complexity.

Key points

Radix sort sorted by the position of the digits, for example the digits of the unit then the decimal and then the hundred.
Each digit pass requires a stable sequencing algorithm, generally counting sort.
Complexity O(d * (n + k)) with d as the number of digits and k as the base of digits (e.g. 10).
Radix sort does not directly compare two elements, as opposed to quick sort or merge sort.
Suitable for integers or strings with relatively uniform digit lengths.

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.