Hi(adsbygoogle = window.adsbygoogle || []).push({});

I'm trying to program a merge sort algorithm on python but it just doesn't work!

I first implemented a fusion algorithm which takes as arguments a list A divided into 2 sorted sub lists A[p..q] and A[q+1..r]. Fusion then returns the list A completely sorted.

This program seems to work, but then my mergeSort which should be easy doesn't work.

Could you have a look at it please?

thanks

Code (Text):

def fusion(A,p,q,r):

"""A[p]<=...A[q] A[q+1]<=...A[r]"""

n1=q-p+1

n2=r-q

L=[]

R=[]

for e in range(n1):

L+=[A[e]]

for e in range(n2):

R+=[A[n2+e+1]]

L+=[float("infinity")]

R+=[float("infinity")]

i=0

j=0

for k in range(p,r+1):

if L[i]<=R[j]:

A[k]=L[i]

i+=1

else:

A[k]=R[j]

j+=1

return A

def mergeSort(A,p,r):

if p<r:

q=int((p+r)/2)

mergeSort(A,p,q)

mergeSort(A,q+1,r)

fusion(A,p,q,r)

return A

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Merge sort

**Physics Forums | Science Articles, Homework Help, Discussion**