[FIXED] Is it possible to sort a list with reduce?

Issue

I was given this as an exercise. I could of course sort a list by using sorted() or other ways from Python Standard Library, but I can't in this case. I think I'm only supposed to use reduce().

from functools import reduce
arr = [17, 2, 3, 6, 1, 3, 1, 9, 5, 3]
sorted_arr = reduce(lambda a,b : (b,a) if a > b else (a,b), arr)

The error I get:

TypeError: '>' not supported between instances of 'tuple' and 'int'

Which is expected, because my reduce function inserts a tuple into the int array, instead of 2 separate integers. And then the tuple gets compared to an int...

Is there a way to insert back 2 numbers into the list, and only run the function on every second number in the list? Or a way to swap the numbers with using reduce()?

Documentation says very little about the reduce function, so I am out of ideas right now. https://docs.python.org/3/library/functools.html?highlight=reduce#functools.reduce

Solution

Here is one way to sort the list using reduce:

arr = [17, 2, 3, 6, 1, 3, 1, 9, 5, 3]
sorted_arr = reduce(
    lambda a, b: [x for x in a if x <= b] + [b] + [x for x in a if x > b],
    arr,
    []
)
print(sorted_arr)
#[1, 1, 2, 3, 3, 3, 5, 6, 9, 17]

At each reduce step, build a new output list which concatenates a list of all of the values less than or equal to b, [b], and a list of all of the values greater than b. Use the optional third argument to reduce to initialize the output to an empty list.

Answered By - pault