具有非递归合并的递归合并排序

Question

我正在尝试编写递归合并排序算法，但我的合并算法不是递归的。

我被告知要在下面的函数中使用以下参数。

def merge(left_buffer, right_buffer, data):
    
    "Merges two sets of data together by comparison"
    print("MERGING",left_buffer,"and",right_buffer)
    #Dual iteration
    m = 1
    n = 1
    k = 0
    j = 0
    for i in range(len(data)):
        if len(left_buffer) == 0:
            data[i] = right_buffer[k]
            k+=1
        elif len(right_buffer) == 0:
            data[i] = left_buffer[j]
            j += 1
        elif left_buffer[0] < right_buffer[0]:
            data[i] = left_buffer[0]
            left_buffer = left_buffer[1:]
            
        else:
            data[i] = right_buffer[0]
            right_buffer = right_buffer[1:]
    print('Result of the merge:',data)

这是我将两个数据集合并到另一个数据集中的功能。

然后是我的递归合并排序算法：

def merge_sort(data):
    "Merge sort recursion"
    if len(data) == 1:
        return [data[0]]
    else:
        half_length = len(data)//2
        left_half = data[0:half_length]
        right_half = data[half_length:]
        
        #Only sorting the left side
        left = merge_sort(left_half)
        right = merge_sort(right_half)
        
        return merge(left,right,data)

我收到的主要问题是，在最终合并两个列表时，我发现我正在合并 None 类型。

我不知道如何解决这个问题。

可能是我的合并算法不对，不过我导师说没问题。

Answer 1

你的 merge 方法没有 return 任何东西，所以当你的 merge_sort 方法 returns 时，它也 returns None.

这些 None 值被传递到 left 和 right，然后您将它们传递到您的 merge 方法。

也许您希望 merge_sort 方法进行合并，然后 return 合并数据？即：

    merge(left,right,data)
    return data

或者，您可以修改 merge，以便它 return 合并数据，方法是在其末尾添加行 return data。

具有非递归合并的递归合并排序

Recursive Merge Sort with non-recursive merge

python

recursion

mergesort