Lazy sort (was Re: Schwartzian transform)

Mallory van Achterberg stommepoes at
Wed Aug 13 13:20:26 BST 2014

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.


More information about the mailing list