CODEWITHSUNDEEP
pythonpython-3.xalgorithmsortingmergesort
deKaV
deKaV

Reputation: 15

Why this Merge Sort does not work properly?

I need to implement Merge Sort using Python 3. I coded it. But It doesn't give proper output. Can anybody check it please? Here my code is,

def mergeSort(A, p, r): 
    if p < r:
        q = (p + r) // 2
        mergeSort(A, p, q)
        mergeSort(A, q+1, r)
        Merge(A, p, q, r)

def Merge(A, p, q, r):
    i = 1
    j = q+1
    k = 0
    TEMP = [0] * (r+1)

    while i <= q and j <= r:
        if A[i] <= A[j]:
            TEMP[k] = A[i]
            k += 1
            i += 1
        else:  
            TEMP[k] = A[j] 
            k += 1
            j += 1
    if (j > r) :
        for t in range(0, q-1):
            A[r-t] = A[q-t]

    for t in range(0, k-1):
       A[p+t] = TEMP[t+1]

A = [15, 16, 13, 10, 19, 18]
mergeSort(A, 0, len(A)-1)
print(A)

Thank you

Upvotes: 1

Views: 101

Answers (2)

Abhinav Mathur
Abhinav Mathur

Reputation: 8101

The error lies in the Merge() function.

  1. Initialisation of i=p and not i=1
  2. After the while loop terminates, there's a chance that either i<q or j<r. We need to accommodate those cases as well.
  3. Size of array TEMP was incorrect.
    Corrected Merge Function:
def Merge(A,p,q,r):
    i = p
    j = q+1
    k=0
    TEMP =  [0]*(r-p+1)
    
    while i <= q and j <= r:
        if A[i] <= A[j]:
            TEMP[k] = A[i]
            k += 1
            i += 1
        else:  
            TEMP[k] = A[j] 
            k += 1
            j += 1
    while i<=q:
        TEMP[k] = A[i]
        k+=1 
        i += 1
    while j<=r:
        TEMP[k] = A[j]
        k+=1 
        j += 1

    for t in range (p,r+1):
       A[t] = TEMP[t-p]

Note: Please try using more meaningful variable names.

Upvotes: 0

unlut
unlut

Reputation: 3775

The way you perform merge looks weird (to me), but I will correct on what you have so far.

1- Initialization value of i is wrong, it should be:

i = p

because i is the first element you will look in array A.

2- Initialization value of size of TEMP array is wrong, it should be:

(r - p + 1)

3- There seems a mistake in filling in TEMP array and/or replacing A array elements, here is the fixed code. I wrote a comment about the part after first while loop to indicate what needs to be done at that point.

def mergeSort(A,p,r): 
    if p < r:
        q = (p+r)//2
        mergeSort(A,p,q)
        mergeSort(A,q+1,r)
        Merge(A,p,q,r)

def Merge(A,p,q,r):
    i = p
    j = q+1
    k=0
    
    
    TEMP =  [0]*(r - p + 1)

    while i <= q and j <= r:
        if A[i] <= A[j]:
            TEMP[k] = A[i]
            k += 1
            i += 1
        else:  
            TEMP[k] = A[j] 
            k += 1
            j += 1
    
    """
        There are currently 2 cases
    1- i > q, means we exhausted left but there are elements in the right
    2- j > r, means we exhausted right but there are elements in the left
    """
    if (j > r):
        #  copy elements at the left side to temp
        while (i <= q):
            TEMP[k] = A[i]
            i += 1
            k += 1
    else:
        #  copy elements at the right side to temp
        while (j <= r):
            TEMP[k] = A[j]
            j += 1
            k += 1
    
    
    #  replace elements in A with elements in TEMP
    for t in range(k):
        A[p+t] = TEMP[t]



A = [15,16,13,10,19,18]
mergeSort(A,0,len(A)-1)
print(A)

Upvotes: 1

Related Questions