Time ComplexityLesson 50Free preview

Radix Sort

This lesson is part of DSA · All levels

Summary

Radix sort runs counting sort as the largest number of digits, so its complexity is O(d * (n + k)) with d the number of digits and k the base. Compared to quick sort, radix sort can be faster for large integers with finite ranges. But this advantage is lost when d or k is increased.

Key points

Complexity with d digits and k bases
Use a stable sort count for each digit
The bounce for data is large with a finite number of digits
Space complexity O(n + k)

Full lesson

Code examples and quizzes

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