Two-way Merge splits the file contents into parts where their size, \(M\), could be held by the main memory. Those parts will be sorted using one of the 202203102004 and we will pair those parts into runs which will be stored into two separate drives or tapes. We will merge two parts by comparing them sequentially until we have hit the end of the run. Follow the recursive rule, we will repeat the steps stated before until we have obtained a sorted result.
Analysis
- It is optimal to have 4 drives or tapes in using Two-way Merge. Two of them used as input, the other two used as output. Their role is interchangeable depends on the run.
- It will require \(\lceil \log(\frac{N}{M}) \rceil\) passes.
- This could be further optimised by 202203111148#