Merge K sorted trade logs with a heap

Question

Each of your k exchange gateways writes a log already sorted by timestamp. You need one globally sorted stream for replay. Merge the k sorted lists into one sorted list. Do better than concatenating and re-sorting. What is the cost?

Accepted Answer

Concatenating all N items and sorting is O(N \log N) and throws away the fact that each list is already ordered. Instead keep a min-heap of the current front element of each list. The heap always holds at most k entries, so its top is the global next value. Pop it, emit it, and push the next element from that same list. Store each heap entry as (value, listindex, elementindex) so you know which list to advance, and the indices break ties deterministically without comparing anything else. Tracing the example: the heap starts as fronts {1, 2, 3}. Pop 1 (from list 0), push its successor 4; pop 2…

Merge K sorted trade logs with a heap

Your answer

More Coding questions