Python3 - 合并排序实现

Question

我正在尝试自己实现 mergeSort，但返回列表的顺序仍然不正确。我一定是遗漏了什么(尤其是在合并步骤中)，有人可以帮我看看是什么吗？

这是我的代码:

def merge(left_half, right_half):
    """
    Merge 2 sorted lists.

    :param left_half:       sorted list C
    :param right_half:      sorted list D
    :return:                sorted list B
    """
    i = 0
    j = 0

    B = []

    for item in range(len(left_half) + len(right_half)):

        while i < len(left_half) and j < len(right_half):

            if left_half[i] <= right_half[j]:
                B.insert(item, left_half[i])
                i += 1
            else:
                B.insert(item, right_half[j])
                j += 1

    B += left_half[i:]
    B += right_half[j:]

    print("result: ", B)

    return B


def mergeSort(A):
    """
    Input:      list A of n distinct integers.
    Output:     list with the same integers, sorted from smallest to largest.

    :return:    Output
    """

    # base case
    if len(A) < 2:
        return A

    # divide the list into two
    mid = len(A) // 2
    print(mid)

    left = A[:mid]      # recursively sort first half of A
    right = A[mid:]     # recursively sort second half of A

    x = mergeSort(left)
    y = mergeSort(right)
    return merge(x, y)


print(mergeSort([1, 3, 2, 4, 6, 5]))

在最后一次合并之前，我正确地收到了两个列表 [1, 2, 3] 和 [4, 5, 6]，但我的最终结果是 [3, 2, 1, 4, 5, 6]。

Answer 1

在 for 循环的第一次迭代中，您完全遍历了其中一个列表，但总是在索引 0 处插入。

你不想插入一个元素，你总是想追加它。这样就不需要 for 循环了。

这是您的代码的固定版本:

def merge(left_half, right_half):
    """
    Merge 2 sorted arrays.

    :param left_half:       sorted array C
    :param right_half:      sorted array D
    :return:                sorted array B
    """
    i = 0
    j = 0

    B = []

    while i < len(left_half) and j < len(right_half):
        if left_half[i] <= right_half[j]:
            B.append(left_half[i])
            i += 1
        else:
            B.append(right_half[j])
            j += 1

    B += left_half[i:]
    B += right_half[j:]

    print("result: ", B)

    return B


merge([1, 2, 3], [4, 5, 6])
# result:  [1, 2, 3, 4, 5, 6]