Lazy sort (was Re: Schwartzian transform)

[Mallory van Achterberg]

On Wed, Aug 13, 2014 at 01:28:57PM +0200, Abigail wrote:
> [1] Well, it may depend on what definition of lazy you mean. Obviously,
>     you can't "lazyly" [3] 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 ]
> 
> [3] Is this a real word?
> 

"Lazily", yes.

-Mallory