Python3 - mergeSort implementation

Question

I'm trying to implement mergeSort on my own, but the order of the returned list is still not correct. I must be missing something (especially by the merge step), could someone pls help me what it is?

Here is my code:

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]))

Before the last merge I receive the two lists [1, 2, 3] and [4, 5, 6] correctly, but my final result is [3, 2, 1, 4, 5, 6].

Answer 1

In the first iteration of your for-loop, you entirely traverse one of the lists, but always insert at index 0.

You do not want to insert an element, you always want to append it. This then makes the for-loop unecessary.

Here is a fixed version of your code:

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]