Type the MERGE inner loop (pick the smaller front element)

Answer

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

Each comparison emits exactly one element, so the loop runs ≤ n times; after it, one side is exhausted and the remainder of the other is appended directly. Using `<=` (not `<`) keeps equal keys in left-then-right order — that is what makes merge sort stable.