# date: 2025.09.20

# [How can I efficiently merge two sorted lists in Python without using merge() or heapq? - Stack Overflow](https://stackoverflow.com/questions/79770326/how-can-i-efficiently-merge-two-sorted-lists-in-python-without-using-merge-or)


def merge_1(a: list, b: list) -> list:
    a = a.copy()
    b = b.copy()

    result = []

    while True:

        if (not a) or (not b):  # if one is empty (or both are empty)
            # if a:
            #    result += a
            # else:
            #    result += b
            result += a + b
            break
        else:
            if a[0] <= b[0]:
                result.append(a.pop(0))
            else:
                result.append(b.pop(0))

    return result


def merge_1b(a: list, b: list) -> list:
    a = a.copy()
    b = b.copy()

    result = []

    while a and b:
        if a[0] <= b[0]:
            result.append(a.pop(0))
        else:
            result.append(b.pop(0))

    # if one of them is still not empty (or both are empty)
    if a or b:
        # if a:
        #    result += a
        # else:
        #    result += b
        result += a + b

    # if a:
    #    result += a
    # elif b:
    #    result += b
    # # else: print('both empty')

    return result


def merge_2(a: list, b: list) -> list:

    len_a = len(a)
    len_b = len(b)

    index_a = 0
    index_b = 0

    result = []

    while True:

        if (index_a >= len_a) or (
            index_b >= len_b
        ):  # if one is empty (or both are empty)
            # if index_a < len(a):
            #    result += a[index_a:]
            # else:
            #    result += b[index_b:]
            result += a[index_a:] + b[index_b:]
            break
        else:
            if a[index_a] <= b[index_b]:
                result.append(a[index_a])
                index_a += 1
            else:
                result.append(b[index_b])
                index_b += 1

    return result


def merge_recursion(a: list, b: list) -> list:
    # if (not a) and (not b):  # if both are empty
    #     return []

    # if not a:
    #     return b
    # if not b:
    #     return a

    if (not a) or (not b):  # if one is empty (or both are empty)
        # if a:
        #    return a
        # else:
        #    return b
        return a + b

    # if a[0] <= b[0]:
    #     return [a[0]] + merge_recursion(a[1:], b)
    # else:
    #     return [b[0]] + merge_recursion(a, b[1:])

    head_a, *tail_a = a
    head_b, *tail_b = b

    if head_a <= head_b:
        return [head_a] + merge_recursion(tail_a, b)
    else:
        return [head_b] + merge_recursion(a, tail_b)


a = [1, 2, 3, 7, 8, 9]
b = [1, 4, 6, 9, 12]
print(f"{a = }")
print(f"{b = }")

print(merge_1(a, b))
print(merge_2(a, b))
print(merge_recursion(a, b))

print(f"{a = }")
print(f"{b = }")