Hacker News new | past | comments | ask | show | jobs | submit login

There 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




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: