Merge sort in descending order in Python

Question

I'm very new to programming and Python, and I try to understand the merge sort.

I'm trying to implement a merge sort function. I want it to work both in ascending (reverse = False) and descending (reverse = True) order. I want to implement the reverse part myself, I don't want to use a built-in method such as reverse().

I switched the '<' into a '>' in the if statement of the first while loop. However, when I run the program with reverse = True and lst = [2, 4, 1, 3, 8, 5], I get the following:

[3, 5, 8, 1, 2, 4]

The desired output would be:

[8, 5, 4, 3, 2, 1]

Does someone know how I could change my function so that it works also in descending order?

def merge(lst, reverse=False):

    if len(lst) < 2:
        return lst

    middle = len(lst) // 2
    left = merge(lst[:middle])
    right = merge(lst[middle:])

    i, j, k = 0, 0, 0

    if reverse:    
        while i < len(left) and j < len(right):
            if left[i] >= right[j]:
                lst[k] = left[i]
                i += 1
            else:
                lst[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            lst[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            lst[k] = right[j]
            j += 1
            k += 1

    else:
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                lst[k] = left[i]
                i += 1
            else:
                lst[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            lst[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            lst[k] = right[j]
            j += 1
            k += 1

    return lst 

lst = [2, 4, 1, 3, 8, 5]
print(merge(lst, True))
´´´

Answer 1

You don't propagate the switch into the recursion. These lines:

left = merge(lst[:middle])
right = merge(lst[middle:])

should be

left = merge(lst[:middle], reverse)
right = merge(lst[middle:], reverse)

EDIT:

I don't want to use built-in method

Also, just for fun, the list of builtin functions you are using (I might have forgotten some): list.__len__, int.__lt__, int.__floordiv__, list.__getitem__, int.__ge__, int.__add__, list.__setitem__, int.__le__, int.__str__, and obviously, print. Getting away from the builtins is not very easy :P