-2

I am trying to implement python Merge Sort, but for some reason when merging it does not sort it correctly at all. I am trying to turn Pseudo code into Python code and I am failing miserably. If anyone can help, I'd really appreciate it. I have tried to debug it and I am just confused.

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

def merge(A, p, q, r): # Issue with sorting
    n1 = q - p + 1
    n2 = r - q
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = A[p + i]
    for j in range(0, n2):
        R[j] = A[q + j]
    L.append(infinity)
    R.append(infinity)
    i = 0
    j = 0
    for k in range(p,r):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1

Example Input:

['date', 'apple', 'banana', 'cucumber', 'acorn', 'aaaa']

Example Output:

['banana', 'acorn', 'aaaa', 'cucumber', 'date', 'date']

mergeSort psuedocode

merge pseudocode

2
  • Please read ericlippert.com/2014/03/05/how-to-debug-small-programs and minimal reproducible example, and study the code carefully. We do not provide a debugging service. Try to make sure you understand what should happen at each step, and check what actually does happen instead. If you believe the problem is in merge, then figure out example input, expected and actual output for just the merge; then break it down into parts and check those. Jan 20 at 1:33
  • Also, consider using more descriptive variable names. Remember, the code is read many more times than it is written, and it especially will be read by you. Jan 20 at 1:35

1 Answer 1

-2

The issue with your implementation is that you are not properly updating the indices when merging the two sublists back together. In the following lines:

for k in range(p,r):
if L[i] <= R[j]:
    A[k] = L[i]
    i = i + 1
else:
    A[k] = R[j]
    j = j + 1

you should be incrementing k instead of i and j. Also the condition inside of the if statement should be L[i] <= R[j] instead of L[i] >= R[j].

Here is the corrected version of the merge function:

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

Also, you have to import the math library and use math.inf instead of infinity.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.