Merge — sorted structures

Merge: heads ஒப்பிட்டு சிறியது advance, output-ல் சேர்.

Try this in Python

def merge_sorted(a: list[int], b: list[int]) -> list[int]:
    i = j = 0
    out: list[int] = []
    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
    out.extend(a[i:])
    out.extend(b[j:])
    return out


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

Key takeaways

• O(n+m) time.
• In-place array merge கடினம்; முதலில் extra space.
• எளிய merge முதலில்.