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




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

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

Search: