Merge two sorted vectors with two pointers

Coding Challenges
, , ,
1

Problem. Given two non-decreasing integer arrays a and b, merge them into one sorted array.

Example:

a = [1, 3, 5, 7]
b = [2, 4, 6, 8]

Answer:

[1, 2, 3, 4, 5, 6, 7, 8]

This is the standard merge step from merge sort.

Solution. Keep one pointer into each input.

  • compare a[i] and b[j]
  • append the smaller one
  • advance that pointer
  • when one side is exhausted, append the remainder of the other side
def merge_two_sorted_vectors(a, b):
	i = 0
	j = 0
	merged = []

	while i < len(a) and j < len(b):
		if a[i] <= b[j]:
			merged.append(a[i])
			i += 1
		else:
			merged.append(b[j])
			j += 1

	merged.extend(a[i:])
	merged.extend(b[j:])
	return merged

Runtime is O(len(a) + len(b)). Extra space is O(len(a) + len(b)) for the output array.

Gotchas.

  • Use <= on one side to keep the merge stable.
  • Do not forget to append the tail of the non-exhausted input.
  • The in-place follow-up is different: you merge from the back if one array has spare capacity.

Run: merge two sorted vectors