Lazy sort (was Re: Schwartzian transform)

[Abigail]

On Wed, Aug 13, 2014 at 01:13:42PM +0200, Mark Overmeer wrote:
> 
> Sort is not lazy (cannot be lazy), so this suffices:

Perls current implementation of sort isn't lazy, but I see no reason
why sort cannot be lazy [1] [2]. If only the first 10 elements of the output
of sort are needed, there's no reason to sort the rest of the list.


[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.

[2] Of course, the answer to "do you want sort to be lazy?" is probably no,
    as it gains you little.

[3] Is this a real word?



Abigail