Slowest sort you can think

What's the slowest non-Bogosort sort you can think of?

For me, it's
- Compute all the n! permutations of the list
- Do a breadth first search of the ordered permutation.
which, if done right, can be O(n*n!logn!).

Instead of the slowest sort possible, try to implement a sort that is as slow as possible while still being reasonably^[1] fast.

1. ^ Definition of “reasonable” here is that if you were to implement said sort in a closed-source program distributed for the general public, no one would notice something strange was going on.