# The Merge

> Chaos in. Order out.

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

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given two already-sorted lists a and b, return a single sorted list containing all their elements. Do NOT use sorted() or sort(). Use the O(n+m) merge procedure.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **two-pointer merge** technique, the building block of merge sort and distributed stream merging. It verifies that candidates can achieve O(n + m) merging without falling back to concatenation plus sorting.

---

### Break down the requirements

#### Step 1: Set up two pointers

Pointer `i` starts at the beginning of list `a`, pointer `j` at the beginning of list `b`.

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

At each step, append the smaller of `a[i]` and `b[j]` to the result and advance that pointer.

#### Step 3: Append leftover elements

When one list is exhausted, append all remaining elements from the other.

---

### The solution

**Two-pointer linear merge**

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

> **Time and Space Complexity**
>
> **Time:** O(n + m) where n and m are the list lengths. Each element is touched exactly once.
> 
> **Space:** O(n + m) for the merged result.

> **Interviewers Watch For**
>
> Using `<=` preserves stability: equal elements from the first list appear before those from the second. This is important in merge sort and real-world record merging.

> **Common Pitfall**
>
> Concatenating and sorting (`return sorted(a + b)`). This is O((n+m) log(n+m)) and violates the problem constraint that `sort()` is not allowed.

---

## Common follow-up questions

- How would you merge in-place if one array had extra capacity? _(Tests the merge-from-end technique to avoid overwriting.)_
- What if you needed to merge k sorted lists? _(Tests heap-based k-way merge.)_
- How does this relate to merge sort's merge step? _(Tests connecting the subroutine to the full algorithm.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_merge)
- [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.