# The List Merger

> No shortcuts.

Canonical URL: <https://datadriven.io/problems/the_list_merger>

Domain: Python · Difficulty: easy · Seniority: L4

## Problem

Given two sorted lists a and b, return a single sorted merged list. Do not call sort() or sorted(); use O(n+m) merge.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **two-pointer merge technique**, the core of merge sort and stream merging in data pipelines. Interviewers check whether you can merge in O(n + m) without calling `sort()`, which would defeat the purpose of pre-sorted inputs.

---

### Break down the requirements

#### Step 1: Initialize two pointers at the start of each list

Pointer `i` tracks position in the first list, pointer `j` tracks the second.

#### Step 2: Compare and append the smaller element

At each step, compare `list1[i]` and `list2[j]`. Append the smaller one and advance that pointer.

#### Step 3: Drain the remaining elements

When one pointer reaches the end, append all remaining elements from the other list.

---

### The solution

**Two-pointer merge in linear time**

```python
def merge_sorted(list1, list2):
    result = []
    i = 0
    j = 0
    while i < len(list1) and j < len(list2):
        if list1[i] <= list2[j]:
            result.append(list1[i])
            i += 1
        else:
            result.append(list2[j])
            j += 1
    while i < len(list1):
        result.append(list1[i])
        i += 1
    while j < len(list2):
        result.append(list2[j])
        j += 1
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n + m) where n and m are the lengths of the two lists. Each element is compared at most once.
> 
> **Space:** O(n + m) for the merged output list.

> **Interviewers Watch For**
>
> Using `<=` instead of `<` preserves the relative order of equal elements (stability). This matters when merging records with secondary sort keys.

> **Common Pitfall**
>
> Forgetting to drain the remaining elements after one list is exhausted. This truncates the output when the lists have different lengths.

---

## Common follow-up questions

- How would you merge k sorted lists efficiently? _(Tests knowledge of heap-based k-way merge with O(n log k) complexity.)_
- What if the lists were too large to fit in memory? _(Tests external merge sort concepts and streaming I/O.)_
- Can you do this in-place if one list has extra capacity? _(Tests the classic merge-from-end trick used in array problems.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_list_merger)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.