python - Online sorting and removing duplicates on two streams of integers -

suppose i'm receiving 2 streams of integers. each stream of integers (1) not guaranteed in increasing order, , (2) occasionally, 1 or more integers missing first stream present on second stream. example:

stream 1 - 1, 2, 3, 5, 4, 6, 8, 9, 10, ...

stream 2 - 1, 2, 3, 4, 5, 6, 8, 7, 10, ...

what data structures and/or algorithms low space-time complexity constructing sorted stream contains every single integer in union (i.e. duplicates removed) set of both streams? is:

sorted stream - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

of course, naive approach store every result sort in o(n log n), making final pass in linear scan remove consecutive duplicate elements. requires lot of memory , requires both streams terminate before processing can start.

this udp packet sequencer on embedded device, code snippets in c preferable, can read python too.

do know integers we're getting, or arbitrary?

you're going need sort @ point, don't see way avoid o(n lg n). best bet heapsort designed sort-as-you-go approach. if value there, don't add it.

(obviously, instead of sorting, you'd adding element heap each time.)