What is the time complexity of this atrocious algorithm?

This grew out of a discussion of deliberately bad algorithms; credit to benneh on the xkcd forums for the pseudocode algorithm, which I've translated to Python so you can actually run it:

def sort(list):
    if len(list) < 2:
        return list
    else:
        if list[0] <= minimum(list[1:]):
            return list[0:1] + sort(list[1:])
        else:
            return sort(list[1:] + list[0:1])

def minimum(list):
    return sort(list)[0]

I'm interested in working out the worst-case, best-case and average-case time complexity, but I've found myself insufficiently practiced to do so. I originally thought it would be O(n!), which would be equivalent to cycling through all possible permutations of the list, but because the results aren't even memoized I believe it's actually worse than that.

Mitigating that is the fact that not all of the recursive calls can possibly be worst-case, so I'm not even sure what the worst-case input is for the function overall.

However—even a sorted input of size 5 results in a total of 64 recursive calls, or $2^{n+1}$. This is best-case time complexity.

What is the worst case input for this algorithm, and what is the time complexity for worst case and average case?

We can write a recurrence relation for this procedure as follows. Let $T(n)$ be the worst-case time for running sort on a list of length $n$. When calling sort on a list of length $n$, we can have up to $n$ recursive calls which rotate the list to the left until its minimum reaches the first entry. Each such call involves an invocation of minimum, and so takes $T(n-1) + O(n)$. The final one descends to sorting a list of length $n-1$. In total, we get the recurrence
$$
T(n) = n T(n-1) + O(n^2).
$$
Opening this recurrence, we get
$$
T(n) = O(n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + \cdots + n!) = O(n!).
$$
(We get $O(n!)$ since the terms decrease very quickly from $n!$ to $n^2$, faster than a geometric series.)

Of course, without giving a matching lower bound, we don't know whether this analysis is tight.

StackExchange Computer Science Q#48482, answer score: 8