- #1
azerty12
- 15
- 0
Hi
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
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:
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
Last edited by a moderator: