Merge sort in Python - `int` object is not iterable

Question

Here is merge sort implementation in Python. I am getting the error int object is not iterable when merge_arrays() function is called. Any suggestions will be highly appreciated.

arr = [1,5,4,7,6,8,3,2,9]

def merge_arrays(_arr_left, _arr_right):
    sorted_arr = []
    left, right = 0, 0

    for i in range(0, len(arr)):
        if (_arr_left[left] < _arr_right[right]):
            sorted_arr.extend(_arr_left[left])
            left += 1
        else:
            print _arr_right[right], right
            sorted_arr.extend(_arr_right[right])
            right += 1

    return sorted_arr

def merge_sort(_arr):
    if (len(_arr) <= 1):
        return _arr

    _arr_left = merge_sort(_arr[:len(_arr)/2])
    _arr_right = merge_sort(_arr[(len(_arr)/2):])

    return merge_arrays(_arr_left, _arr_right)

try:
    merge = merge_sort(arr)
    print merge
except Exception as e:
    print e

Answer 1

As other answers have mentioned, you need to change extent to append. However, as you said in comments, you are getting list index out of range error because you are iterating over the size of arr which is 9 but subarrays have much lesser length. Try changing your merging two arrays code to the following.

while (len(_arr_left) > left) or (len(_arr_right) > right):
        if (len(_arr_left) > left) and (len(_arr_right) > right):
            if (_arr_left[left] < _arr_right[right]):
                sorted_arr.append(_arr_left[left])
                left += 1
            else:
                sorted_arr.append(_arr_right[right])
                right += 1
        elif (len(_arr_left) > left):
            sorted_arr.append(_arr_left[left])
            left += 1
        else:
            sorted_arr.append(_arr_right[right])
            right += 1

As you can see in the above code, we have to test for various conditions. If both subarrays contains elements, then we compare them to each other and append to sorted_arr depending on the value evaluation. If not then we append values from individual sub-arrays. It would have been easier if instead of using left and right, you were using pop so you wouldn;t have to keep tracking of left and right

Finally, here is the working version of your code. You also need to modify return merge_sort(...) to sorted_arr = merge_sort(...) return sorted_arr so it doesn't print everytime it returns sorted_arr