Merge two sorted shelves into one

Two pointers Junior Python 3.13+ Reviewed By Best Latest Apps

Fill the blank

Fill the blank.

Python 3.13
def merge(a: list[int], b: list[int]) -> list[int]:
    i = j = 0
    out: list[int] = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    return ____
print(merge([1, 4], [2, 3, 9]))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A out + a[i:] + b[j:]

Right: at most one of the two tails is non-empty, and both are already sorted.

After the loop one shelf is exhausted, so appending both tails costs nothing extra and keeps the order.

Why not the others?
  • B out. That drops whatever is left on the longer shelf.
  • C sorted(out). out is already sorted; the leftovers are still missing.

30-second answer

Keep one pointer per shelf. Repeatedly take the smaller front item and advance that pointer; when one shelf runs out, append the rest of the other. Every item is taken once, so it is O(n + m) time and O(n + m) for the output.

Practise saying it · 30 s. No recording, just a timer

Explain the merge step and its cost.

Say your answer out loud, then check which of these points you covered:

  • One pointer per list
  • Take the smaller front
  • Append leftovers; O(n + m)

Deep dive

Taking from the left shelf on ties keeps the merge stable, which matters when items carry other data.

This is the merge step of merge sort, and the basis of merging sorted files on disk.

sorted(a + b) is shorter but O((n + m) log(n + m)) and ignores that the inputs are sorted. (Timsort does notice two sorted runs, but say the general cost.)

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def merge_shelves(a: list[int], b: list[int]) -> list[int]:
    i = j = 0
    out: list[int] = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

Common mistakes

  • Forgetting the leftover items once one shelf is empty.
  • Using pop(0) to take the front item, which shifts the whole list each time.

Senior take & follow-ups

Point out the stability choice on ties. It is a small detail that shows care.

Follow-up questions

Think of your answer first, then open the hint.

  1. How would you merge k shelves?

    Show hint

    Keep a heap of the k front items: O(N log k) for N items in total.

  2. How would you merge in place into the first list with spare room at the end?

    Show hint

    Fill from the back, comparing the largest remaining items.

What each operation costs: Arrays · Array Operations

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.