Object of type ‘NoneType’ has no len() in merge sort

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

Leave a Reply

Your email address will not be published. Required fields are marked *