Help Me Debug My Merge Sort Algorithm

[azerty12]

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

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

 

[rcgldr]

A recursive mergesort() like the one you're trying to implement recursively splits up an array into 2 sub-arrays(), and continues to just recurse and split up sub-arrays until sub-arrays have size 1, before any merging occurs. Then the sub-arrays are merged as the call chain is followed back upwards to the original call to mergesort(). Note that the merge() function will require a second buffer, up to the size of the original array.

Example pseudo code: mergesort() splits up the arrays, merge() merges two arrays. Again note that the call to mergesort(left) or mergesort(right) will just recurse until the sub-array size is 1, and only then does merging and return back up the call chain occur.

mergesort(array){
    n = size_of(array)
    if(n <= 1){
        return(array);}
    left = array[(0) ... (n/2 - 1)];
    right = array[(n/2) ... (n-1)];
    left = mergesort(left); 
    right = mergesort(right);
    return( merge(left, right) );
}

A bottom up mergesort() uses iteration instead of recursion. At initialization, it simply considers an array as a list of n sub-arrays of size 1, by setting up indexes or pointers and sub-array size = 1. It allocates a memory buffer for a second copy of the array, then merges all pairs of the sub-arrays in the original buffer to the second buffer, (doubling sub-array size), and then merges from the second buffer back to the original buffer (doubling sub-array size again), until sub-array size is >= original array size. When completed, the mergesort() may return a pointer to which buffer ended up with the sorted data (original or second), or if the sorted data ended up in the second buffer, it could copy it back to the original buffer.

Here are web sites with pseudo code for merge sort.

http://www.algorithmist.com/index.php/Merge_sort

http://en.wikipedia.org/wiki/Merge_sort