How do I change from ascending to descending in MergeSort?-CodePudding

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:

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.

CodePudding user response：

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]: