i was wondering, when i have a list of integers and i need to sort them, and i know that they are integers in 32 bit, can i use radix sort (with counting sort as its stable sort) to sort them in o(n) time?
isn't it just 32 counting sorts using the bits representation on the numbers starting from LSB?
i know that general sorts with no previous knowledge of the numbers take o(nlogn), but isnt the fact that they are 32 bit integers is all i need to make it an o(n) sort?
thanks!
Yep! Radix sort will work fine for unsigned integers, and (with a little bit more work) for signed integers as well.
Interestingly, it will also work for non-NaN, nonnegative floating point numbers if their bits are reinterpreted as integers. (Negative floating point numbers require somewhat more work, and probably aren't worth it.)