Task. Two retrieval shards (or two models) each return a list of (score, doc_id) pairs, sorted by score,
highest first. Return the global top k as a list of doc ids:
- each document at most once, using its highest score if both lists contain it;
- ties broken by
doc_id(ascending) so the output is deterministic.
a = [(0.92, "d3"), (0.81, "d7"), (0.40, "d1")]
b = [(0.88, "d5"), (0.81, "d2"), (0.75, "d7"), (0.10, "d9")]
k = 4 → ["d3", "d5", "d2", "d7"]
ML context. This is the last step of every sharded search: a vector index split across machines, a keyword engine and a vector engine, or several candidate generators in a recommender. Each returns its best results; the aggregator merges them. Doing it in O(k) instead of sorting everything matters when each shard returns thousands of candidates and the request budget is a few milliseconds.