On 01/16/2016 10:28 PM, Ivan Kazmenko wrote:
On Saturday, 16 January 2016 at 15:25:50 UTC, Andrei Alexandrescu wrote:...To summarize: For k<<n we have O(n) average case and O(n log k) worst case. For k~n we have O(n log n) as HeapSort.
The implementation falls back to topNHeap whenever k is within the first or last ~n/8 elements and therefore is Ω(n log n) on average.
