CODEWITHSUNDEEP
pythonmergesort
Nico Mcrae
Nico Mcrae

Reputation: 13

Merge sorting algorithm works for small list but crashes with bigger ones

I'm trying to recreate the merge sorting algorithm and while my code works for lists with length 4 or less when the length gets bigger it crushes.

As you'll see the error says that on some point sorted_right becomes NoneType. I tried debugging it but couldn't understand why this happens. Can anyone help me with this?

My code:

my_list = [5, 35, 10, 1, 0]

def merge_sort(array):
    if len(array) == 1:
        return array
    elif len(array) == 2:
        if array[0] > array[1]:
            array[0], array[1] = array[1], array[0]
        return array
    else:
        sorted_part = []
        left = array[:len(array)//2]
        right = array[len(array)//2:]
        sorted_left = merge_sort(left)
        sorted_right = merge_sort(right)
        for i in range(len(array)):
            if len(sorted_left) == 0:
                sorted_part.extend(sorted_right)
                break
            elif len(sorted_right) == 0:
                sorted_part.extend(sorted_left)
                break
            else:
                if sorted_left[0] < sorted_right[0]:
                    sorted_part.append(sorted_left.pop(0))
                else:
                    sorted_part.append(sorted_right.pop(0))
    print(sorted_part)


merge_sort(my_list)

The error:

[0, 1, 10]
Traceback (most recent call last):
  File "C:\Users\User\PycharmProjects\Mathima 15\askisis 10 merge sort.py", line 32, in <module>
    merge_sort(my_list)
  File "C:\Users\User\PycharmProjects\Mathima 15\askisis 10 merge sort.py", line 21, in merge_sort
    elif len(sorted_right) == 0:
         ^^^^^^^^^^^^^^^^^
TypeError: object of type 'NoneType' has no len()

Process finished with exit code 1

Upvotes: 0

Views: 71

Answers (1)

Chris
Chris

Reputation: 36620

If you're going to use the return value from a recursive function in the function, it needs to return in every scenario. Your else branch has no such return. The solution is simple: return sorted_part.

def merge_sort(array):
    if len(array) == 1:
        return array
    elif len(array) == 2:
        if array[0] > array[1]:
            array[0], array[1] = array[1], array[0]
        return array
    else:
        sorted_part = []
        left = array[:len(array)//2]
        right = array[len(array)//2:]
        sorted_left = merge_sort(left)
        sorted_right = merge_sort(right)
        for i in range(len(array)):
            if len(sorted_left) == 0:
                sorted_part.extend(sorted_right)
                break
            elif len(sorted_right) == 0:
                sorted_part.extend(sorted_left)
                break
            else:
                if sorted_left[0] < sorted_right[0]:
                    sorted_part.append(sorted_left.pop(0))
                else:
                    sorted_part.append(sorted_right.pop(0))
        return sorted_part

The print at the end of the function is extraneous now as it would never be reached.

This also seems like a good place to apply the match/case syntax introduced in Python 3.10.

def merge_sort(array):
    match array:
        case [_]: return array
        case [a, b] if a < b: return array
        case [a, b]: return [b, a]
        case _:
            sorted_part = []
            left = array[:len(array)//2]
            right = array[len(array)//2:]
            sorted_left = merge_sort(left)
            sorted_right = merge_sort(right)
            for i in range(len(array)):
                if len(sorted_left) == 0:
                    sorted_part.extend(sorted_right)
                    break
                elif len(sorted_right) == 0:
                    sorted_part.extend(sorted_left)
                    break
                elif sorted_left[0] < sorted_right[0]:
                    sorted_part.append(sorted_left.pop(0))
                else:
                    sorted_part.append(sorted_right.pop(0))
            return sorted_part

As a sidenote: array is a potentially misleading name for a list.

You may also wish to return a new list in the simpler cases.

        case [_]: return list(array)
        case [a, b] if a < b: return list(array)

Upvotes: 0

Related Questions