Re:Sorting a Billion Numbers with Julia
by nly on Monday March 21, 2016 @11:40PM
(#11334277)
The complexity of fully iterating over a lazily-sorted range is more than 'somewhat slower'. At a guess I'd say it's O(n^2) rather than O(n log n).
[ Parent
| on HN ]
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.
It should stay n log n. A lazy quicksort can get the min element of a list super fast by only working on the partitions relevant to finding the min. As it requires more elements of the list, it can finish sorting the other partitions. It's the exact same algo as usual.