Stream merge: Difference between revisions
Content added Content deleted
(Created page with "{{task}} == Description == === 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 ext...") |
No edit summary |
||
| Line 14: | Line 14: | ||
Common solution: same as above, but keep buffered items and their source descriptors in a [[heap]]. |
Common solution: same as above, but keep buffered items and their source descriptors in a [[heap]]. |
||
== Shell == |
|||
sort --merge source1 source2 sourceN > sink |
|||
Revision as of 09:05, 15 June 2016
You are encouraged to solve this task according to the task description, using any language you may know.
Description
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 solution: same as above, but keep buffered items and their source descriptors in a heap.
Shell
sort --merge source1 source2 sourceN > sink