在merg实现期间获取“类型为'NoneType'的对象没有len（）”

Question

我试图在python中实现mergeSort，但是得到了类型错误。你知道吗

我试着调试代码，但没有成功。你知道吗

def merge(L, R):
    (C, m, n) = ([], len(L), len(R))
    (i,j) = (0,0)

    while i+j < m+n:
        if i == m: # Case 1 -> List A is empty
            C.append(R[j])
            j += 1
        elif j == n: # Case 2 -> List B is empty
            C.append(L[i])
            i += 1
        elif L[i] <= R[j]: # Case 3 -> Head of A is smaller 
            C.append(L[i])
            i += 1
        elif L[i] > R[j]:
            C.append(R[j])
            j += 1
    print(C)

def mergeSort(A, left, right):

    if right - left <= 1: # Base Case
        return(A[left:right])
    if right - left > 1: # Recurive call
        mid = (left+right)//2

        L = mergeSort(A, left, mid)
        R = mergeSort(A, mid, right)

        return(merge(L, R))

如果有人知道我做错了什么，请引导我走正确的路。你知道吗

Answer 1

Is there any more efficient way to implement this

使用一对相互递归的函数（msa2a、msa2b）进行自顶向下的合并排序，以更改合并方向并避免复制数据：

def sort(a):
    if(len(a) < 2):                     # if nothing to do, return
        return
    b = [0] * len(a)                    # allocate b
    msa2a(a, b, 0, len(a))              # merge sort a to a

def msa2a(a, b, low, end):              # merge sort a to a
    if((end - low) < 2):                # if < 2 elements
        return                          #   return
    mid = (low+end)//2                  # set mid point
    msa2b(a, b, low, mid)               # merge sort left  half to b
    msa2b(a, b, mid, end)               # merge sort right half to b
    mrg(b, a, low, mid, end)            # merge halves   from b to a

def msa2b(a, b, low, end):              # merge sort a to b
    if((end - low) < 2):                # if < 2 elements
        b[low] = a[low]                 #   copy 1 element from a to b
        return                          #   return
    mid = (low+end)//2                  # set mid point
    msa2a(a, b, low, mid)               # merge sort left  half to a
    msa2a(a, b, mid, end)               # merge sort right half to a
    mrg(a, b, low, mid, end)            # merge halves   from a to b

def mrg(a, b, ll, rr, ee):              # merge a pair of runs from a to b
    o = ll                              # o = b[]        index
    l = ll                              # l = a[] left   index
    r = rr                              # r = a[] right  index
    while True:
        if(a[l] <= a[r]):               # if a[l] <= a[r]
            b[o] = a[l]                 #   copy a[l]
            o += 1
            l += 1
            if(l < rr):                 #   if not end of left run
                continue                #     continue (back to while)
            b[o:ee] = a[r:ee]           #   else copy rest of right run
            return                      #     and return
        else:                           # else a[l] > a[r]
            b[o] = a[r]                 #   copy a[r]
            o += 1
            r += 1
            if(r < ee):                 #   if not end of right run
                continue                #     continue (back to while)
            b[o:ee] = a[l:rr]           #   else copy rest of left run
            return                      #     and return

自底向上的合并排序只稍微快一点，但是对于这个版本，如果传递的次数是奇数，它会在第一次传递时进行交换，这有助于更进一步。合并函数（mrg）与上面显示的自顶向下合并排序相同。你知道吗

def sort(a):
    if(len(a) < 2):                     # if nothing to do, return
        return
    b = [0] * len(a)                    # allocate b
    mrgsrt(a, b, len(a))

def mrgsrt(a, b, n):
    s = 1                               # assume even pass count
    if((passcnt(n) & 1) == 1):          #  if odd count
        while(s < n):                   #   swap pairs in place
            if(a[s] < a[s-1]):
                a[s-1],a[s] = a[s],a[s-1]
            s = s + 2
        s = 2
    while(s < n):
        ee = 0                          # reset end index
        while(ee < n):                  # setup for next pair of runs
            ll = ee
            rr = ll + s
            if(rr >= n):                #  if only left run copy it
                b[ll:n] = a[ll:n]
                break
            ee = rr + s
            if(ee > n):
                ee = n
            mrg(a, b, ll, rr, ee)
        a,b = b,a                       # swap(a, b)
        s = s << 1                      # double run size

def mrg(a, b, ll, rr, ee):              # merge a pair of runs from a to b
    o = ll                              # o = b[]        index
    l = ll                              # l = a[] left   index
    r = rr                              # r = a[] right  index
    while True:
        if(a[l] <= a[r]):               # if a[l] <= a[r]
            b[o] = a[l]                 #   copy a[l]
            o += 1
            l += 1
            if(l < rr):                 #   if not end of left run
                continue                #     continue (back to while)
            b[o:ee] = a[r:ee]           #   else copy rest of right run
            return                      #     and return
        else:                           # else a[l] > a[r]
            b[o] = a[r]                 #   copy a[r]
            o += 1
            r += 1
            if(r < ee):                 #   if not end of right run
                continue                #     continue (back to while)
            b[o:ee] = a[l:rr]           #   else copy rest of left run
            return                      #     and return

def passcnt(n):                         # return # passes
    i = 0
    s = 1
    while(s < n):
        s = s << 1
        i = i + 1
    return(i)

更快的方法是混合插入+合并排序，将插入排序用于运行<；=64个元素（取决于元素大小）。我没有python代码作为例子。由于Python是解释性的，所以它慢一些，在上面所示的示例合并排序中，Python占用的长度是C++中编译的相同代码的64倍。你知道吗

Answer 2

merge必须返回C，而不是打印它。你知道吗

def merge(L, R):
    (C, m, n) = ([], len(L), len(R))
    (i,j) = (0,0)

    while i+j < m+n:
        if i == m: # Case 1 -> List A is empty
            C.append(R[j])
            j += 1
        elif j == n: # Case 2 -> List B is empty
            C.append(L[i])
            i += 1
        elif L[i] <= R[j]: # Case 3 -> Head of A is smaller 
            C.append(L[i])
            i += 1
        elif L[i] > R[j]:
            C.append(R[j])
            j += 1
    return C