[swiftcoder]

> Radix sort looks fast, with its O(n)O(n) worst-case time complexity. But, if you're using it to sort binary numbers, then there's a hidden constant factor that's usually 32 or 64 (depending on how many bits your numbers are). That's often way bigger than O(\lg(n))O(lg(n)), meaning radix sort tends to be slow in practice.

The constant factor in radix sort isn't the number of bits, it's the number of digits. Since one typically sorts on a computer using 8-bit 'digits', that's a constant factor of 4 or 8 (not 32 or 64).

[ggggtez]

It's the number of bits. You can change to bytes, but you are just hiding another constant factor of 8 by doing that.

[swiftcoder]

If you have a theoretical computer with single-bit registers, sure. Quicksort is also quite slow on such an computer.

[kjeetgill]

And this is why O() notation drops constants. 0(bits) or O(bits/8) aka bytes are the same thing. It's also worth pointing out that in standard comparison sorts, the comparison itself is technically linear to radix too, but is treated as constant. I get why it's dropped but it's worth knowing.

[ggggtez]

Exactly. You can try to compare two bytes, but really you are comparing 8 bits, if you thought about it algorithmically. Maybe those steps are 100% parallel. But it's irrelevant to the big O. You are measuring number of steps, and it's intended to be hardware independent.

[ggggtez]

Big O is hardware independent.