def merge(items1, items2, new_items=[]):
    """Merge given lists of items, each assumed to already be in sorted order,
    and return a new list containing all items in sorted order.
    Running time: O(n)
    Memory usage: O(n)"""
    if not items1 and not items2:
        return new_items
    elif not items1:
        return new_items + items2
    elif not items2:
        return new_items + items1

    if items1[0] < items2[0]:
        new_items.append(items1[0])
        items1 = items1[1:]
    else:
        new_items.append(items2[0])
        items2 = items2[1:]

    return merge(items1, items2, new_items)