3 ms·
I was thinking about how this (and other "physical sorts" mentioned by commenters) sorts instantly by using a physical property of the members, and I began to c
by _bxg1 7y ago
I was thinking about how this (and other "physical sorts" mentioned by commenters) sorts instantly by using a physical property of the members, and I began to consider what the computer equivalent would be of "physical sorting".
I think you could take the sort values, use them as memory addresses (or array offsets), and write the original index of each value into its corresponding pointer, then go back and iterate through that entire chunk of memory to find each of them. That might technically be linear time? Really N + M, where N is the number of values and M is their full range. It would have hilariously inefficient usage of memory and a pretty low cap on the range of possible sort values, but still.
- ladberg 7y agoThis is basically a 1-deep radix sort, where each memory location is a bucket.
- aasasd 7y agoIt can really be used if the range is small, though I'm not sure I've met such a case where it would be practical. Back in the day, a notable feature of this algo was that it does zero comparisons, which were slower than straightforward crunching. I think you can also use a large bitmap if all you want is sorted values. BTW, Bloom filters work on a quite similar idea, and they come in handy in database setups.