K

#### KrzysiekYESS

##### Guest

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

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]=LA[k]=L

i=i+1

else:

A[k]=R[j]

j=j+1

k=k+1

while i<nL:

A[k]=Li=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):

Li=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 Lfor 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] = LA[k] = L

i += 1

else:

A[k] = R[j]

j += 1

k += 1

while i < nL:

A[k] = Li += 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>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>