I’m implementing an usual merge sort algorithm in python as follows but got an unexpected type error.
from typing import List
def merge(arr1: List[int], arr2: List[int]) -> List[int]:
sorted_arr = []
i, j = 0, 0
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
sorted_arr.append(arr1[i])
i = i + 1
else:
sorted_arr.append(arr2[j])
j = j + 1
sorted_arr += arr1[i:]
sorted_arr += arr2[j:]
def merge_sort(arr: List[int]):
if len(arr) == 1:
return arr
mid = len(arr) // 2
left_arr = merge_sort(arr[:mid])
right_arr = merge_sort(arr[mid:])
return merge(left_arr, right_arr)
The error says this:
while i < len(arr1) and j < len(arr2): TypeError: object of type 'NoneType' has no len()
I have no idea why the type error can occur on the while loop. Could anyone help me with this? Thanks.
Answer
The problem is that you haven’t explicitly returned anything from the merge() method and by default it returns None if nothing is returned explicitly.
Return the sorted_arr at the end of the merge() method as:
def merge(arr1: List[int], arr2: List[int]) -> List[int]:
sorted_arr = []
i, j = 0, 0
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
sorted_arr.append(arr1[i])
i = i + 1
else:
sorted_arr.append(arr2[j])
j = j + 1
sorted_arr += arr1[i:]
sorted_arr += arr2[j:]
return sorted_arr # return the sorted_arr