Merging sorted sequences
In one line
Walk two sorted sequences with one pointer each, always taking the smaller front element, to produce one sorted result in O(n + m).
What it is
Merging combines two sorted sequences into one sorted sequence. One pointer sits at the front of each input; at every step you compare the two front elements, output the smaller one and advance that pointer. When one input runs out, the rest of the other is already sorted and is copied as is.
The same walk answers related questions: the intersection or union of two sorted lists, and merging in place into an array that has spare room at the end (by filling from the back). It is the core step of merge sort and of how databases and storage engines combine sorted data.
Why interviewers ask
Merging is a building block for merge sort, k-way merging, interval problems and linked-list questions, and 'merge sorted array' is a frequent warm-up. Interviewers watch for correct handling of leftovers, stability with equal elements (use <=) and the fill-from-the-back trick that avoids overwriting data in place.
How it works
- 1Set i = 0 on a and j = 0 on b, and an empty output.
- 2While both have elements: if a[i] <= b[j], output a[i] and i += 1; otherwise output b[j] and j += 1. Using <= takes from a first on ties, which keeps the merge stable.
- 3When one input is exhausted, append the rest of the other; it is already sorted and all its values are at least the last one output.
- 4Every element is output exactly once: O(n + m) time, O(n + m) space for the output.
- 5In place, when a has m values followed by n empty slots: start both read pointers at their last real values and a write pointer at the very end, and place the larger value there. Writes land in slots already read or empty, so nothing is lost.
- 6Intersection: when the fronts are equal, output it and advance both; otherwise advance the pointer at the smaller value.
Worked example · Merge a = [1, 4, 7] and b = [2, 3, 9]
- i = 0 (1), j = 0 (2): 1 <= 2, output 1, i = 1. Output [1].
- i = 1 (4), j = 0 (2): take 2, j = 1. Output [1, 2].
- i = 1 (4), j = 1 (3): take 3, j = 2. Output [1, 2, 3].
- i = 1 (4), j = 2 (9): take 4, i = 2. Output [1, 2, 3, 4].
- i = 2 (7), j = 2 (9): take 7, i = 3. a is exhausted.
- Append the rest of b: [9]. Final [1, 2, 3, 4, 7, 9] after 5 comparisons, each element placed exactly once.
- In place version: nums1 = [1, 4, 7, _, _, _], nums2 = [2, 3, 9]. Compare 7 and 9, write 9 at index 5; 7 vs 3, write 7 at 4; 4 vs 3, write 4 at 3; 1 vs 3, write 3 at 2; 1 vs 2, write 2 at 1; nums2 done, and 1 is already in place.
Picture it
Two queues of people sorted by height merging into one line at a single door: the attendant always lets in the shorter of the two people at the front. When one queue empties, the rest of the other queue walks straight in, already in order.
Reference code
def merge(a, b):
i = j = 0
out = []
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps equal items in order (stable)
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1
out.extend(a[i:]) # at most one of these is non-empty
out.extend(b[j:])
return out
def merge_into(nums1, m, nums2, n):
# nums1 holds m values followed by n spare slots; fill from the back
i, j, w = m - 1, n - 1, m + n - 1
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[w] = nums1[i]
i -= 1
else:
nums1[w] = nums2[j]
j -= 1
w -= 1
merge takes the smaller front element each step and uses <= so equal elements keep their original order (stability), then appends whatever remains. merge_into fills nums1 from the back so it never overwrites an unread value; it only loops while nums2 has values, because any remaining nums1 values are already in place. Both are O(n + m) time; merge_into uses O(1) extra space.
Key patterns
Merge two sorted arrays or lists
When: Combine sorted inputs, the merge step of merge sort
How: Compare fronts, take the smaller (<= for stability), append leftovers.
Merge in place from the back
When: First array has spare room at its end
How: Pointers at the last real values and at the last slot; write the larger value and move left.
Intersection and union
When: Common elements of two sorted lists, or their union without duplicates
How: Equal fronts: output and advance both. Otherwise advance the smaller.
k-way merge
When: More than two sorted inputs (k lists, sorted files)
How: Min-heap of each input's front element; pop, output, push that input's next. O(N log k).
Merge on intervals
When: Two sorted lists of intervals, find overlaps
How: Overlap is [max(starts), min(ends)] if valid; advance the interval that ends first.
Real-world use
Python and Java sorting (Timsort)
Python's sorted() and Java's sort for objects use Timsort, which finds already sorted runs in the data and merges them pairwise, so nearly sorted inputs sort in close to O(n).
External sorting in databases
When a sort does not fit in memory, PostgreSQL (and other databases) sort chunks into sorted runs on disk and then merge the runs, reading each run sequentially.
Merge joins
PostgreSQL and SQL Server can join two tables already sorted on the join key (for example via an index) with a merge join: one pointer per table, advancing the smaller key, in O(n + m).
LSM-tree compaction
RocksDB, LevelDB and Cassandra store data in sorted files (SSTables) and periodically merge them, keeping the newest version of each key, which is a multi-way merge of sorted sequences.
In a project
An observability team must show one combined, time-ordered log view from two services whose logs are each already sorted by timestamp, with millions of lines per hour.
- Open both log streams and keep one read pointer (current line) per stream.
- Repeatedly output the line with the earlier timestamp and advance that stream; on equal timestamps, take service A first so the order is stable and repeatable.
- When one stream ends, copy the rest of the other directly.
- Generalise to many services with a min-heap of each stream's current line (k-way merge), still streaming without loading everything into memory.
Impact: The combined view is produced in a single streaming pass, O(n + m), using constant memory per stream, instead of loading and re-sorting all logs, which cut view generation from minutes to seconds.
Trade-offs
Use it when
- Inputs are already sorted (or cheap to sort) and you need sorted output
- Data is streamed or too large for memory: merging reads each input sequentially
- You need intersections or unions of sorted lists without hashing
Avoid it when
- Inputs are unsorted and you only need membership: a hash set is O(n + m) without sorting
- There are many inputs: use a heap-based k-way merge instead of merging pairs repeatedly in a chain
- One input is tiny and the other huge: binary-searching each small element into the big one can be faster
Cost: Two-way merge: O(n + m) time; O(n + m) output space, or O(1) extra when merging in place from the back. k-way merge with a heap: O(N log k).
Common mistakes
- Forgetting to append the leftover elements after the main loop.
- Using < instead of <=, which breaks stability (equal elements from b move ahead of a), important for merge sort on records.
- Merging in place from the front, which overwrites values of nums1 not yet read.
- In merge_into, looping while i >= 0 instead of while j >= 0, which can leave nums2 values uncopied.
- Merging k lists one by one into a growing result, which costs O(N * k) instead of O(N log k) with a heap or pairwise merging.
Interview questions
Quick revision
- Compare fronts, take the smaller, advance that pointer.
- Use <= to keep the merge stable.
- Append leftovers when one side runs out.
- O(n + m) time; each element placed once.
- In place with spare room: fill from the back, loop while the second array has values.
- Intersection: equal -> output and advance both, else advance smaller.
- k inputs: min-heap, O(N log k).
- Merge is the core of merge sort, Timsort, external sort and LSM compaction.
Check yourself
1. What is the time complexity of merging sorted arrays of lengths n and m?
2. Why do in-place merges into nums1 fill from the back?
3. Merging [1, 3] (list A) and [1, 2] (list B) with 'if a[i] <= b[j]', which 1 is output first?
4. What is the best approach to merge k sorted lists with N total elements?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.