Also, if you know the distribution of the values, you can achieve sorting or pre-sorting by a letting an order-preserving "hash-function" fill a table, so O(N).
Yes, that is true for any sorting algorithm. We can always achieve better results if we preprocess the data on some parameters. Thanks for your feedback, will try to incorporate this in the later version!
The function h(x) places the item ordered directly into a table, instead of waiting x timesteps.
The optimal choice of h(x), x ∈ X, is a bounded monotonic function that inverts the distribution of X, so that h(x) is uniformly distributed. It preserves the order and spreads h(x) evenly in the hash-space.