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

Taught in

References