OiO.lk Community platform!

Oio.lk is an excellent forum for developers, providing a wide range of resources, discussions, and support for those in the developer community. Join oio.lk today to connect with like-minded professionals, share insights, and stay updated on the latest trends and technologies in the development field.
  You need to log in or register to access the solved answers to this problem.
  • You have reached the maximum number of guest views allowed
  • Please register below to remove this limitation

MergeSort implementation doesn't work correctly

  • Thread starter Thread starter KrzysiekYESS
  • Start date Start date
K

KrzysiekYESS

Guest
I've been trying to implement MergeSort in Python from the book Introduction to Algorithms and I don't know why this version is not working correctly (it does compile but the list isn't sorted properly). My code:

Code:
import math
def MergeSort(A,p,r):
    if(p>=r):
        return
    q=math.floor((p+r)/2)
    MergeSort(A,p,q)
    MergeSort(A,q+1,r)
    Merge(A,p,q,r)
def Merge(A,p,q,r):
    nL=q-p
    nR=r-q
    L=[0]*nL
    R=[0]*nR
    for i in range(0,nL):
        L[i]=A[p+i]
    for j in range(0,nR):
        R[j]=A[q+j]
    i=0
    j=0
    k=p
    while i < nL and j < nR:
        if L[i] <= R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1
        k=k+1
    while i<nL:
        A[k]=L[i]
        i=i+1
        k=k+1
    while j < nR:
        A[k]=R[j]
        j=j+1
        k=k+1

A=[20,52,35,22,90,12,5]
MergeSort(A,0,len(A))
print(A)

the problem is this part:

Code:
    if(p>=r):
        return
    q=math.floor((p+r)/2)
    MergeSort(A,p,q)
    MergeSort(A,q+1,r)

when it isn't q+1 the recursion never ends but with q+1 it doesn't give correct output the code that works:

Code:
import math

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

def Merge(A, p, q, r):
    nL = q - p
    nR = r - q
    L = [0] * nL
    R = [0] * nR
    for i in range(nL):
        L[i] = A[p + i]
    for j in range(nR):
        R[j] = A[q + j]
    i = 0
    j = 0
    k = p
    while i < nL and j < nR:
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1
    while i < nL:
        A[k] = L[i]
        i += 1
        k += 1
    while j < nR:
        A[k] = R[j]
        j += 1
        k += 1

A = [20, 52, 35, 22, 90, 12, 5]
MergeSort(A, 0, len(A))
print(A)

I would like to have my version working because it's the most similar to the pseudocode from the book and also learn why this one isn't right since I'm only starting working with recursions.
<p>I've been trying to implement MergeSort in Python from the book Introduction to Algorithms and I don't know why this version is not working correctly (it does compile but the list isn't sorted properly).
My code:</p>
<pre><code>import math
def MergeSort(A,p,r):
if(p>=r):
return
q=math.floor((p+r)/2)
MergeSort(A,p,q)
MergeSort(A,q+1,r)
Merge(A,p,q,r)
def Merge(A,p,q,r):
nL=q-p
nR=r-q
L=[0]*nL
R=[0]*nR
for i in range(0,nL):
L=A[p+i]
for j in range(0,nR):
R[j]=A[q+j]
i=0
j=0
k=p
while i < nL and j < nR:
if L <= R[j]:
A[k]=L
i=i+1
else:
A[k]=R[j]
j=j+1
k=k+1
while i<nL:
A[k]=L
i=i+1
k=k+1
while j < nR:
A[k]=R[j]
j=j+1
k=k+1

A=[20,52,35,22,90,12,5]
MergeSort(A,0,len(A))
print(A)
</code></pre>
<p>the problem is this part:</p>
<pre><code> if(p>=r):
return
q=math.floor((p+r)/2)
MergeSort(A,p,q)
MergeSort(A,q+1,r)
</code></pre>
<p>when it isn't q+1 the recursion never ends but with q+1 it doesn't give correct output
the code that works:</p>
<pre><code>import math

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

def Merge(A, p, q, r):
nL = q - p
nR = r - q
L = [0] * nL
R = [0] * nR
for i in range(nL):
L = A[p + i]
for j in range(nR):
R[j] = A[q + j]
i = 0
j = 0
k = p
while i < nL and j < nR:
if L <= R[j]:
A[k] = L
i += 1
else:
A[k] = R[j]
j += 1
k += 1
while i < nL:
A[k] = L
i += 1
k += 1
while j < nR:
A[k] = R[j]
j += 1
k += 1

A = [20, 52, 35, 22, 90, 12, 5]
MergeSort(A, 0, len(A))
print(A)

</code></pre>
<p>I would like to have my version working because it's the most similar to the pseudocode from the book and also learn why this one isn't right since I'm only starting working with recursions.</p>
 
Top