4 ms·
If you are dealing with numbers, then you can do this is true O(n) time with radix-select. (Basically do a MSB radix sort and only do subsequent passes in the
by ekelsen 9y ago
If you are dealing with numbers, then you can do this is true O(n) time with radix-select. (Basically do a MSB radix sort and only do subsequent passes in the bucket where you know k must be).
- sova 9y agoWow. can't believe no one ever mentioned this before, Most Significant Bit bucketification would cut down seek time a lot.