Merging sorted lists/iterators/generators into one stream of values...

[Delaney, Timothy (Tim)]

Lasse Vågsæther Karlsen wrote:

> I need to merge several sources of values into one stream of values.
> All of the sources are sorted already and I need to retrieve the
> values from them all in sorted order.
> 
> In other words:
> s1 = [10, 20, 30, 40, 50]
> s2 = [15, 25]
> s3 = [17, 27, 37]
> 
> for value in ???(s1, s2, s3):
>      print value
> 
> will print out 10, 15, 17, 20, 25, 27, 30, 37, 40, 50 in that order.
> 
> The sources are cursors retrieving data from several databases, not
> from the same server, and there's a potential for a large number of
> rows from several of the sources. As such, any method that would load
> it all into memory and sort it is no good as it would too much memory.

I would suggest retrieving the first element from each data source. Then for the smallest element, keep retrieving from that data source until it is no longer the smallest element, at which time you switch to the data source with the smallest element.

Tim Delaney