Re:Sorting a Billion Numbers with Julia
by im3w1l on Tuesday March 22, 2016 @02:39AM
(#11334785)
Finding sorted(array)[k] is possible in linear (even worst case!) time. Using that n times would as you note take n^2 time. But we could employ a trick. Once we have been asked for log n elements, and have thus already spent n log n time, we could then sort the array.
[ Parent
| on HN ]
There are no comments on this comment yet.