Lazy sort (was Re: Schwartzian transform)
Mallory van Achterberg
stommepoes at stommepoes.nl
Wed Aug 13 13:20:26 BST 2014
On Wed, Aug 13, 2014 at 01:28:57PM +0200, Abigail wrote:
>  Well, it may depend on what definition of lazy you mean. Obviously,
> you can't "lazyly"  sort an infinite list, as you need to process
> all elements at least once to be able to return a first element.
> But using, for instance, heapsort, you can return the first k elements
> of a list in sorted order in O (N + k log N) time, which beats
> O (N log N) if k << N.
[ snip ]
>  Is this a real word?
More information about the london.pm