Merge join

How: Sorts both tables by the join condition and merges the results like a zipper. For very large datasets, it splits the dataset into chunks, sorts each chunk in memory, writes each sorted chunk into a temporary file on disk, and finally does a multi-way merge of the sorted files on disk.

When: It's used when at least one input dataset is pre-sorted or for datasets larger than the working memory.

Tip: Ensure datasets are pre-sorted or can be sorted efficiently.

Complexity:

• for pre-sorted inputs: O(M+N) time. O(1) space
• otherwise: O(MlogM + NlogN) time. O(M+N) space