Is it possible to sort a list with reduce?

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.

I think you're misunderstanding how reduce works here. Reduce is synonymous to right-fold in some other languages (e.g. Haskell). The first argument expects a function which takes two parameters: an accumulator and an element to accumulate.

Let's hack into it:

arr = [17, 2, 3, 6, 1, 3, 1, 9, 5, 3]
reduce(lambda xs, x: [print(xs, x), xs+[x]][1], arr, [])

Here, xs is the accumulator and x is the element to accumulate. Don't worry too much about [print(xs, x), xs+[x]][1] – it's just there to print intermediate values of xs and x. Without the printing, we could simplify the lambda to lambda xs, x: xs + [x], which just appends to the list.

The above outputs:

[] 17
[17] 2
[17, 2] 3
[17, 2, 3] 6
[17, 2, 3, 6] 1
[17, 2, 3, 6, 1] 3
[17, 2, 3, 6, 1, 3] 1
[17, 2, 3, 6, 1, 3, 1] 9
[17, 2, 3, 6, 1, 3, 1, 9] 5
[17, 2, 3, 6, 1, 3, 1, 9, 5] 3

As we can see, reduce passes an accumulated list as the first argument and a new element as the second argument.（If reduce is still boggling you, How does reduce work? contains some nice explanations.)

Our particular lambda inserts a new element into the accumulator on each "iteration". This hints at insertion sort:

def insert(xs, n):
    """
    Finds first element in `xs` greater than `n` and returns an inserted element.
    `xs` is assumed to be a sorted list.
    """
    for i, x in enumerate(xs):
        if x > n:
            return xs[:i] + [n] + xs[i:]

    return xs + [n]

sorted_arr = reduce(insert, arr, [])
print(sorted_arr)

This prints the correctly sorted array:

[1, 1, 2, 3, 3, 3, 5, 6, 9, 17]

^{Note that a third parameter to reduce (i.e. []) was specified as we initialise the sort should with an empty list.}