1

I am getting a TypeError when I try to use recursion in my merge sort function. I am trying to return a tuple containing a list and a number. If only the list is returned, then my function is able to sort properly and return a sorted list, however.

My desired output:

([1,2,3,4,5,6,7,8,9,10,...],100)

My merge function takes a list and simple lambda expression to compare two numbers.

def merge_s(list_s, ordering):

    if len(list_s) < 2:
        return list_s, 100
    result = []
    mid = int(len(list_s) / 2)
    y = merge_s(list_s[:mid], ordering)
    z = merge_s(list_s[mid:], ordering)
    i = 0
    j = 0
    first_item = ''
    second_item = ''

    while i < len(y) and j < len(z):
        first_item = y[i]
        second_item = z[j]
        if ordering(second_item, first_item):
            result.append(z[j])
            j += 1
        else:
            result.append(y[i])
            i += 1
    result += y[i:]
    result += z[j:]
    return result, 100

My main function:

from random import shuffle
def main():

    for i in range(10):
        data = list(range(100))
        shuffle(data)
        comp = lambda a, b: a < b #my compare function
        (sorted_data, _) = merge_s(data, comp)
        test = (sorted_data,_)
    print(test)

However, I am getting the error:

TypeError: '<' not supported between instances of 'int' and 'list'

1 Answer 1

2

merge_s returns: result, 100

However when you get the results of the recursive calls:

y = merge_s(list_s[:mid], ordering)
z = merge_s(list_s[mid:], ordering)

You treat it as if merge_s just returned result instead of a tuple of (result, 100)

while i < len(y) and j < len(z):
    first_item = y[i]
    second_item = z[j]
    if ordering(second_item, first_item):

This has a very simple fix where you just extract the result for y and z:

y, _ = merge_s(list_s[:mid], ordering)
z, _ = merge_s(list_s[mid:], ordering)

And with that fix your output is:

([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60,61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99], 100)
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.