Merge Sort 2 Lists Finding Common Elements

Question

For an assignment we have been asked to write a function that takes as inputs 2 lists and then returns a list containing all of names that were in both 'list 1' and 'list 2'.

It has been asked to be done using a merge sort based algorithm. What I have got so far returns the correct list, however I am making too many comparisons to get this list. VoterList is a specified class given to us so that we don't use normal python lists. Only VoterName objects (what the two input lists are made of) are able to be appended to a VoterList. The lists being passed in are both in lexicographical order.

Any advice on how to reduce my comparisons is welcomed. Thank you.

from classes import VoterList
def fraud_detect_merge(first_booth_voters, second_booth_voters):

    fraud = VoterList()
    length_first = len(first_booth_voters)
    length_second = len(second_booth_voters)
    first_booth_position = 0
    second_booth_position = 0
    comparisons = 0
    while first_booth_position < length_first:

        if second_booth_position == length_second:
            first_booth_position += 1
            second_booth_position = 0

        else:
            name_comparison = first_booth_voters[first_booth_position]
            comparisons += 1

            if second_booth_voters[second_booth_position] == name_comparison:
                fraud.append(second_booth_voters[second_booth_position])
                first_booth_position += 1
                second_booth_position = 0

            else:
                second_booth_position += 1


    return fraud, comparisons

Answer 1

It is not clear what your input is, is it already sorted? You are being given lists. Check out what operations can be performed on lists and you will find the pop() operation. This removes one item from the list and give you its value. As the lists are both in order the following approach can be used:

def fraud_detect_merge(first_booth_voters, second_booth_voters):
    fraud = VoterList()
    comparisons = 0

    first_booth_voters.sort()     # if not already sorted
    second_booth_voters.sort()    # if not already sorted

    first = first_booth_voters[0]
    second = second_booth_voters[0]

    while first_booth_voters and second_booth_voters:
        comparisons += 1

        if first == second:
            fraud.append(first)
            first = first_booth_voters.pop(0)
            second = second_booth_voters.pop(0)
        elif first < second:
            first = first_booth_voters.pop(0)
        else:
            second = second_booth_voters.pop(0)

    return fraud, comparisons