Merge Two Sorted Files with Bounded Memory

Merge Two Huge Sorted Files You are given two input files, A and B, each independently sorted in non-decreasing order by an integer key. Each line contains one record; for this problem, a record can be treated as an integer. Both input files, as well as the output file, may be much larger than memory. Produce an output file containing all records from A and B in non-decreasing order. Duplicates must be preserved. Requirements Do not load an entire input file or the entire output into memory. Read inputs sequentially and write the output sequentially. Use O(1) extra memory excluding file buffers, or O(B) including configurable buffers of size B. Explain how to reduce network I/O and small read/write overhead when files are on a distributed file system or object storage. Example A: 1 2 4 8 B: 1 3 5 8 9 Output: 1 1 2 3 4 5 8 8 9 Scale Each file may contain billions of records and be TB-scale. Memory cannot hold either complete file. Each input is already sorted. Example Input 1 2 4 8 1 3 5 8 9 Output 1 1 2 3 4 5 8 8 9