2 ms·
not with radix sort, but you can do better when your elements are integers, even if there there are a lot of them, i.e. even when n ~ 2^32.
by utopcell 3y ago
not with radix sort, but you can do better when your elements are integers, even if there there are a lot of them, i.e. even when n ~ 2^32.
- xdavidliu 3y agointeresting; got an example or link? What exact asymptotic form do you mean by "better" here?
- utopcell 3y agoThere are many such algorithms. For example, [1] is expected linear time, deterministic O(nlglgn) time and linear space. Note that the proposed ML (micro-)algorithms rely heavily on the fact that they are sorting 32-bit or 64-bit integers because they are using conditional moves. A conditional move avoids a branch by converting the instruction to a no-op when the condition doesn't hold. This is fine when moving 4 or 8 bytes because it can be done in a single clock cycle, but you can't apply the same technique when sorting larger objects. [1] https://dl.acm.org/doi/pdf/10.1145/225058.225173 https://dl.acm.org/doi/pdf/10.1145/225058.225173