# Mergesort in Python optimization

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

• One thing killing performance is bound to be allocating a fresh buffer in each and every call. – greybeard Jan 6 at 8:32