radix sort
A non-comparison sort that sorts integers one digit at a time, using a stable sort such as counting sort for each digit.
In more detail
LSD (least significant digit) radix sort starts with the ones digit and works up; stability ensures earlier passes are not undone. It takes O(d(n + k)) time for d digits of base k. It needs integer-like keys of bounded length, so it does not apply directly to floating-point numbers or arbitrary strings.
Related terms
- counting sort — A non-comparison sort for small non-negative integers that counts how many times each value occurs and then writes the values back out in order.
- stable sort — A sort that keeps items with equal keys in the same relative order they had before sorting.
Taught in
- Counting And Radix Sort: Beating N Log N — Algorithms & Data Structures for Working Engineers