3 ms·
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).
by yobbo 2y ago
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).
- animeshchouhan 2y agoYes, 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!
- yobbo 2y agoSleepsort is like a hash-based sort using sleep(x) instead of a hash function h(x). You can see more here: https://pages.cs.wisc.edu/~siff/CS367/Notes/sorting.html 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.