Skip to content

Stable in-place merging [ref]

Problem

  • Merge [(1, "L1"), (2, "L2")] with [(1, "R1"), (3, "R2")].
  • Choose the left record when equal keys meet by using <=.
  • Copy any unconsumed suffix after one input is exhausted.

Python solution

left = [(1, "L1"), (2, "L2")]
right = [(1, "R1"), (3, "R2")]
res = []
i = j = 0

while i < len(left) and j < len(right):
    if left[i][0] <= right[j][0]:
        res.append(left[i])
        i += 1
    else:
        res.append(right[j])
        j += 1

res.extend(left[i:])
res.extend(right[j:])
res  # [(1, 'L1'), (1, 'R1'), (2, 'L2'), (3, 'R2')]

(res[0][1], res[1][1])  # ('L1', 'R1')

res[-1]  # (3, 'R2')