Where Merge Sort Shows Up — Files, DBs, Parallel

Beyond “sort an array,” merge sort’s merge step powers counting cross-list inversions, external sorting, and stable multi-key sorts in real software stacks.

Why this shows up in the real world

Git merges ordered change lists; while not pure numeric merge sort, the “merge two ordered views” intuition appears everywhere. Streaming analytics windows often keep partial sorted segments that must be combined hourly. GPU radix passes aside, CPU-side batch jobs still merge sorted CSV chunks before deduplication.

Core idea (explained for students)

Whenever data arrives partitioned but sorted within partitions, merging is the glue. Complexity often becomes O(n log p) for p partitions if balanced. Learn to recognize merge-shaped loops in interview stories: two sorted iterators, one output—same skeleton as merge step.

Try this in Python

chunks = [[1, 5, 9], [2, 6], [3, 4, 7, 10]]
import heapq

print(list(heapq.merge(*chunks)))

Common mistakes

• Merging more than two streams without heap—can explode time.
• Ignoring I/O cost in external merge—dominates wall clock.
• Assuming stability propagates through multiple merges without checking tie policy.

Key takeaways

• Merge step is a reusable subroutine.
• External sorting = sort runs + k-way merge.
• Practice converting business merges to two-pointer code.