Merge Logic for Two Sorted Lists

Two pointers consume smaller head each step—O(n+m) merge.

Try this in Python

def merge(a, b):
    i = j = 0
    out = []
    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 out + a[i:] + b[j:]

print(merge([1, 3], [2, 4]))

Key takeaways

• Stability: use <= to keep merges stable if required.
• Inversions count can piggyback on merge.
• Linked lists mimic same logic with node hops.