Introduction

Combining multiple sorted lists into one sorted output is a classic merge problem. In code golf, shortest syntax wins, but a compact solution is only useful if it is still correct on duplicates, empty inputs, and uneven list lengths. Knowing both golf-style and algorithmic approaches helps you choose the right tradeoff for your context.

Start with the Golf-Friendly Baseline

The shortest approach in many languages is flatten then sort.

lists = [[1, 4, 9], [2, 5], [3, 6, 7]]
result = sorted(x for lst in lists for x in lst)
print(result)

This is concise and correct for any input shape where elements are comparable. Complexity is based on total element count and full sort cost. For small and medium inputs, this can be perfectly acceptable and very readable.

Use Heap-Based K-Way Merge for Scale

If inputs are already sorted, a heap-based k-way merge avoids sorting all elements from scratch.

1import heapq
2
3def merge_sorted_lists(lists):
4    heap = []
5    for list_index, lst in enumerate(lists):
6        if lst:
7            heap.append((lst[0], list_index, 0))
8    heapq.heapify(heap)
9
10    merged = []
11    while heap:
12        value, li, ei = heapq.heappop(heap)
13        merged.append(value)
14
15        next_index = ei + 1
16        if next_index < len(lists[li]):
17            next_value = lists[li][next_index]
18            heapq.heappush(heap, (next_value, li, next_index))
19
20    return merged
21
22print(merge_sorted_lists([[1, 4, 9], [2, 5], [3, 6, 7]]))

This keeps only one frontier element per list in the heap, which scales well when there are many large lists.

Streaming Output Instead of Building Full Result

If consumers can process values incrementally, yield values as a stream.

1import heapq
2
3def merge_iter(lists):
4    heap = []
5    for list_index, lst in enumerate(lists):
6        if lst:
7            heap.append((lst[0], list_index, 0))
8    heapq.heapify(heap)
9
10    while heap:
11        value, li, ei = heapq.heappop(heap)
12        yield value
13
14        next_index = ei + 1
15        if next_index < len(lists[li]):
16            heapq.heappush(heap, (lists[li][next_index], li, next_index))
17
18print(list(merge_iter([[1, 3], [2, 4], [0, 5]])))

Streaming is useful when merged output is large or consumed by another iterator pipeline.

Preserve Determinism with Ties

Equal values from different lists should still produce deterministic order for reproducible tests. Including list index and element index in heap tuples gives stable tie-breaking.

That is why tuple fields are typically (value, list_index, element_index) and not only value.

Benchmark with Representative Input

Do not assume one strategy is always fastest. Python sorted is highly optimized in native code and can outperform heap merge for small data sizes.

A minimal benchmark pattern:

1import random
2import time
3
4lists = [sorted(random.randint(0, 10_000) for _ in range(2000)) for _ in range(40)]
5
6start = time.perf_counter()
7sorted(x for lst in lists for x in lst)
8print("flatten_sort", time.perf_counter() - start)
9
10start = time.perf_counter()
11merge_sorted_lists(lists)
12print("heap_merge", time.perf_counter() - start)

Measure against your actual workload size and list count.

Production Style Versus Golf Style

For code golf posts, shortest valid expression is the goal. For production code, readability and tests matter more than character count.

A practical approach:

• Keep a concise one-liner for explanation and simple scripts.
• Use named heap merge function in library code.
• Add unit tests for empty lists, duplicates, and mixed lengths.

Example tests:

assert merge_sorted_lists([]) == []
assert merge_sorted_lists([[], [2], []]) == [2]
assert merge_sorted_lists([[1, 1], [1]]) == [1, 1, 1]

Common Pitfalls

• Assuming flatten-and-sort is always the best choice at large scale.
• Forgetting empty sublists and causing index errors in heap initialization.
• Losing duplicate values during merge logic.
• Ignoring deterministic tie handling and getting unstable test output.
• Over-optimizing for character count in production paths.

Summary

• Flatten-and-sort is compact and often strong for small inputs.
• Heap-based k-way merge scales better for many pre-sorted lists.
• Generator-based merge supports streaming and lower memory use.
• Stable tie handling improves reproducibility.
• Choose strategy based on context: golf brevity or production maintainability.