Merging multiple sorted sequences.

Terry Reedy tjreedy at udel.edu
Wed Apr 12 22:34:35 EDT 2017


On 4/12/2017 7:15 PM, Erik wrote:
> Hi Peter,
>
> On 12/04/17 23:42, Peter Otten wrote:
>> Erik wrote:
>>
>>> I need to be able to lazily merge a variable number of already-sorted(*)
>>> variable-length sequences into a single sorted sequence.
>>
>> https://docs.python.org/dev/library/heapq.html#heapq.merge
>
> AFAICT (looking at the Python 3.5 heapq implementation, albeit very
> briefly), it seems like that is a greedy algorithm. Am I missing something?

Yes.  Read the source to see what it does and why one or more inputs 
could be infinite iterators.  Hint: it does *not* heapify everything at 
once.

--
Terry Jan Reedy



More information about the Python-list mailing list