3 ms·

but the number of elements in the array is also a 32 or 64 bit integer, so you still cannot do better than O(n log n) even with fancy radix sort or whatever

• 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 ago
    interesting; got an example or link? What exact asymptotic form do you mean by "better" here?
    • utopcell 3y ago
      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 https://dl.acm.org/doi/pdf/10.1145/225058.225173