Lazy sort (was Re: Schwartzian transform)
abigail at abigail.be
Wed Aug 13 12:28:57 BST 2014
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  . If only the first 10 elements of the output
of sort are needed, there's no reason to sort the rest of the list.
 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.
 Of course, the answer to "do you want sort to be lazy?" is probably no,
as it gains you little.
 Is this a real word?
More information about the london.pm