def merge(items1, items2):
    """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) Passes over each element once
    Memory usage: O(n) Makes a new list for all the elements
    """
    ind_1, ind_2 = 0, 0
    new_list = []
    # Repeat until one list is empty
    while ind_1 <= len(items1) - 1 and ind_2 <= len(items2) - 1:
        # Find minimum item in both lists and append it to new list
        if items1[ind_1] <= items2[ind_2]:
            new_list.append(items1[ind_1])
            ind_1 += 1
        else:
            new_list.append(items2[ind_2])
            ind_2 += 1
    # Append remaining items in non-empty list to new list
    if ind_1 <= len(items1) - 1:
        new_list.extend(items1[ind_1:])
    elif ind_2 <= len(items2) - 1:
        new_list.extend(items2[ind_2:])
    return new_list