CODEWITHSUNDEEP
pythonalgorithmsortingmergesort
Lezou Dali
Lezou Dali

Reputation: 11

Can anyone tell me what's wrong with my Merge Sort in Python?

It's giving me the following errors and I know it has to do with the fact that the left or right array are sometimes None. I just don't know why that's the case. The error:

File "/Users/lezoudali/Documents/Algorithms/sort.py", line 62, in merge

    while i < len(left) and j < len(right):

TypeError: object of type 'NoneType' has no len()

My code:

from random import randint 

alist = [randint(1,50) for i in range(10)]

def merge(left, right):
  i = j = 0 
  result = []
  while i < len(left) and j < len(right):
    if left[i] < right[j]:
        result.append(left[i])
        i += 1
    else:
        result.append(right[j])
        j += 1
  while i < len(left):
    result.append(left[i])
    i += 1
  while j < len(right):
    result.append(right[j])
    j += 1

def mergesort(alist):
  if len(alist) == 1:
    return alist
  mid = len(alist) // 2
  left = mergesort(alist[:mid])
  right = mergesort(alist[mid:])
  return merge(left, right)

print mergesort(alist)

Upvotes: 0

Views: 186

Answers (1)

Lezou Dali
Lezou Dali

Reputation: 11

It turns out I was not returning my result from the merge function. So the function was return None, which was the problem I was having. Thanks senderle! 

  def merge(left, right):
    i = j = 0 
    result = []
    while i < len(left) and j < len(right):
      if left[i] < right[j]:
        result.append(left[i])
        i += 1
      else:
        result.append(right[j])
        j += 1
    while i < len(left):
      result.append(left[i])
      i += 1
    while j < len(right):
      result.append(right[j])
      j += 1 
    return result

Upvotes: 1

Related Questions