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).
You can see more here: https://pages.cs.wisc.edu/~siff/CS367/Notes/sorting.html
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.