Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

How do I change from ascending to descending in MergeSort?

I can properly run my code to sort an array to in ascending order, but when I try to do descending I keep getting index out of range. I’ve been trying to debug it and run through my for loops to figure out the problem, but I’m getting no where. Any suggestions are welcome, thank you.

def merge_sort(arr, beg, end):
    if beg < end:
        mid = (beg +  end) // 2
        merge_sort(arr, beg, mid)
        merge_sort(arr, mid + 1, end)
        merge(arr, beg, mid, end)

def merge(A, beg, mid, end):
    n1 = mid - beg + 1
    n2 = end - mid

    L = [0] * (n1 + 1)
    R = [0] * (n2 + 1)

    for i in range(0, n1):
        L[i] = A[beg + i]

    for j in range(0, n2):
        R[j] = A[mid + 1 + j]

    L[n1] = float('inf') 
    R[n2] = float('inf') 

    i = 0
    j = 0

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

    return A

myList = [26,54,93,17,77,31,44,55,20]
merge_sort(myList, 0, len(myList) - 1)
print(myList)

My output for this MergeSort is: [17, 20, 26, 31, 44, 54, 55, 77,93]
which is in ascending order, I want my output to be the opposite:
[93, 77, 55, 54, 44, 31, 26, 20, 17]

For these lines of code:

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

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

I did switch out the <= with > but I get index range errors.

>Solution :

For descending, the sentinel values need to be max negative values:

    L[n1] = -float('inf')            
    R[n2] = -float('inf') 

For stability (maintain original order for equal values):

            if L[i] >= R[j]:
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading