def merge(list1, list2):
    """Merge two sorted (nondecreasing values) list of tuples,
    as we do in merge sort
    Both lists must be nonempty.
    """
    if not list1:
        return list2
    if not list2:
        return list1
    new_list = []
    size1 = len(list1)
    size2 = len(list2)
    j = 0
    k = 0
    key1, val1 = list1[j]
    key2, val2 = list2[k]
    while True:
        if val2 < val1:
            new_list.append((key2,val2))
            k = k+1
            if k>=size2:
                new_list.extend(list1[j:size1])
                break
            key2, val2 = list2[k]
        else:
            new_list.append((key1,val1))
            j = j+1
            if j>=size1:
                new_list.extend(list2[k:size2])
                break
            key1, val1 = list1[j]
    return new_list