Merge Top-K Results From Multiple Shardsmedium

Merge Top-K Results From Multiple Shards

medium RAG & Retrieval 15 min

NumPy allowed · plain Python earns 10 bonus points

A query retrieves context

Embedding similarity ranks the documents before generation.

Open lesson →

01query

02embed

03retrieve

04context

What is RAG?→ embed →top context

retrieval.md44%

rag-systems.md33%

agents.md24%

Cosine-like similarity scores ranked before context assembly

Implement the scatter-gather merge step every distributed vector search does: each shard returns its own top-k, and the query router must merge them into one global top-k.

Task

Implement merge_shard_topk(shard_results, k). Each element of shard_results is a list of (id, score) tuples, already sorted descending by score within its shard (higher score = more relevant). Merge all shards' results and return the global top-k (id, score) tuples sorted descending by score; ties broken by id ascending.

Function Signature

merge_shard_topk(shard_results: list[list[tuple]], k: int) -> list[tuple]

Examples

Example 1: two shards, simple merge
Input: shard_results = [[['a', 0.9], ['b', 0.5]], [['c', 0.8], ['d', 0.3]]]
k = 3
Output: [['a', 0.9], ['c', 0.8], ['b', 0.5]]

Example 2: tie broken by id
Input: shard_results = [[['z', 0.5]], [['a', 0.5]]]
k = 2
Output: [['a', 0.5], ['z', 0.5]]

Example 3: k smaller than total results
Input: shard_results = [[['a', 0.9], ['b', 0.8], ['c', 0.7]]]
k = 1
Output: [['a', 0.9]]

Constraints

each shard's list is individually pre-sorted descending
1 <= k

Python3Saved ✓

def merge_shard_topk(shard_results: list[list[tuple]], k: int) -> list[tuple]:

# Your implementation here

pass

Case 1: two shards, simple merge

Input: shard_results = [[['a', 0.9], ['b', 0.5]], [['c', 0.8], ['d', 0.3]]]
k = 3

Expected: [['a', 0.9], ['c', 0.8], ['b', 0.5]]

Case 2: tie broken by id

Input: shard_results = [[['z', 0.5]], [['a', 0.5]]]
k = 2

Expected: [['a', 0.5], ['z', 0.5]]

Case 3: k smaller than total results

Input: shard_results = [[['a', 0.9], ['b', 0.8], ['c', 0.7]]]
k = 1

Expected: [['a', 0.9]]