Merge k sorted lists: heap vs divide-and-conquer — which is better for n=10k?

Question presented to candidate: "You have k sorted Python lists holding about 10,000 numbers in total. Would you merge them with a heap or with divide and conquer? Code both, tell me their complexity, and tell me which one you would actually ship."

What a strong answer should cover:

• Both are O(N log k) time; sequential merging is O(N·k) and is the trap to avoid.
• Heap: O(k) extra memory, works on streams, can stop early; divide and conquer: fewer comparisons (one per item per level) and no heap at all.
• Clarifying what "n = 10k" means: total items N, or number of lists k.
• Python details: heapq is a min-heap on a plain list; entries must be tuples with a tie-breaker index so Python never compares the payload; heapq.merge already exists in the standard library.
• An honest measurement: at this size in CPython the C-implemented heapq beats a pure-Python merge loop, and sorted() beats both.

Clarifying questions expected:

• Is 10,000 the total item count or the number of lists?
• Arrays or linked lists; all in memory or streams?

Code / implementation expected: Yes — a heapq-based k-way merge and a recursive pairwise merge, in Python 3.