2
\$\begingroup\$

I am currently writing mergesort in Python and have implemented it to work. I have noticed, though, that it is very slow compared to the standard sorted() method. I understand it will always be faster but I am open to suggestions in terms of optimization.

def merge(left,right):
    sortedArray=[]
    l_idx,r_idx=0,0 #set index for left and right array
    #compare values of left and right array
    while l_idx<len(left) and r_idx<len(right):
        if(left[l_idx] < right[r_idx]):
            sortedArray.append(left[l_idx])
            l_idx+=1
        else:
            sortedArray.append(right[r_idx])
            r_idx+=1
    if l_idx==len(left):
        sortedArray.extend(right[r_idx:])
    else:
        sortedArray.extend(left[l_idx:])
    return sortedArray

def mergesort(A):
    if len(A)<=1:
        return A
    middle=len(A)//2
    left,right=mergesort(A[:middle]),mergesort(A[middle:])
    return merge(left,right) 

Thank you for any feedback

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.