 2-stream merge
 Read two sorted streams of items from external source (e.g. disk, or network), and write one stream of sorted items to external sink.
 Common algorithm: keep 1 buffered item from each source, select minimal of them, write it, fetch another item from that stream from which the written item was.
 N-stream merge
 The same as above, but reading from    N    sources.
 Common algorithm: same as above, but keep buffered items and their source descriptors in a heap.


Assume streams are very big. You must not suck them whole in the memory, but read them as streams.




without js -- file i/o
include builtins/pqueue.e
 
procedure add(integer fn, pq)
    object line = gets(fn)
    if line=-1 then
        close(fn)
    else
        pq_add({fn,line}, pq)
    end if
end procedure
 
-- setup (optional/remove if files already exist)
constant data = {"Line 001\nLine 008\nLine 017\n",
                 "Line 019\nLine 033\nLine 044\nLine 055\n",
                 "Line 019\nLine 029\nLine 039\n",
                 "Line 023\nLine 030\n"},
         filenames = {"file1.txt","file2.txt","file3.txt","file4.txt"}
                    -- (or command_line()[3..$] if you prefer)
 
for i=1 to length(filenames) do
    integer fn = open(filenames[i], "w")
    if fn<0 then crash("cannot open file") end if
    puts(fn, data[i])
    close(fn)
end for
 
-- initilisation
integer pq = pq_new()
for i=1 to length(filenames) do
    integer fn = open(filenames[i], "r")
    if fn<0 then crash("cannot open file") end if
    add(fn,pq)
end for
 
-- main loop
while not pq_empty(pq) do
    {integer fn, string line} = pq_pop(pq)
    puts(1,line)
    add(fn, pq)
end while
pq_destroy(pq)
 
-- cleanup (optional/remove if files already exist)
for i=1 to length(filenames) do
    {} = delete_file(filenames[i])
end for
