I have used following code to create a merge sort following a tutorial from youtube. It works fine for various examples. But if I try to run it on a list as defined below, it starts running an infinite loop. Can someone tell me what is wrong here?

This is the code I used

def merge(A,B): #merge A[0:m],B[0:n]
    (C,m,n)= ([],len(A),len(B))
    (i,j)=(0,0) # Current positions in A and B
    while i j<m n: # i j is number of elements merged so far
        if i==m: # A is empty
            C.append(B[j])
            j=j 1
        elif j==n: # B is empty
            C.append(A[i])
            i= i 1

        elif A[i]<B[j]: # head of A is smaller than head of B
            C.append(A[i])
            i=i 1
        elif A[i]>B[j]: # head of B is smaller than head of A
            C.append(B[j])
            j= j 1
    return C


def merge_sort(A,left,right): #sort the slice A[left,right]
    if right - left <=1 :# base case
        return A[left:right]
    if right - left> 1: #recursive call
        mid= (left right)//2
        L= merge_sort(A,left,mid)
        R= merge_sort(A,mid,right)
        return merge(L,R)
A= list(range(100,1,-2))
B= list(range(40,183,2))
D= A B
print(merge_sort(D,0,len(D)))

CodePudding user response：

You're missing the case where A[i] == B[j] which causes infinite loop.

Simple fix:

        elif A[i]<=B[j]: # head of A is smaller than head of B
            C.append(A[i])
            i=i 1