type after creation in recursive loop for merge sort

I am trying to understand algorithms by writing them myself. While trying to replicate merge sort I have run into some trouble: left & right return none-type and an error is raised for the len(left) in the first while loop. I have been fighting with the code and could not figure out what I was missing? Shouldn't it just loop until the size of left and right lists reduce to 1 which would allow them to get out of the if loop and continue with the next part of the function?

def merge_sort(A):

    if len(A) < 2:
        return A
    else:
        mid= len(A)//2
        left= merge_sort(A[:mid])
        right= merge_sort(A[mid:])

    i = j = 0
    sortedlist = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sortedlist.append(left[i])
            i+=1
        else:
            sortedlist.append(right[j])
            j+=1
    while i < len(left):
        sortedlist.append(left[i])
        i+=1
    while j < len(right):
        sortedlist.append(right[j])
        j+=1
    print(str(sortedlist))

---

all you need to do is add a return statement (the last statement in the code below):

def merge_sort(A):

    if len(A) < 2:
        return A
    else:
        mid= len(A)//2
        left = merge_sort(A[:mid])
        right = merge_sort(A[mid:])

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

    # NEED TO RETURN THE LIST HERE!
    return sortedlist

if your function does not return anything statements like left = merge_sort(A[:mid]) will assign None to left instead of the sorted (half of the) list.

you could then test that with:

import random

lst = list(range(15))
random.shuffle(lst)
ret = merge_sort(lst)
print(ret)

---

Your function doesn't contain a return statement. You should add return sortedlist at it's end.

链接地址: http://www.djcxy.com/p/53496.html

上一篇: 访问集合的唯一元素

下一篇: 在递归循环中为合并排序创建后键入