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!).

Random sort. Try a combination and check if it's right; if not, repeat. It has unpredictable time constraints, and doesn't necessarily generate the correct result, ever. Making it effectively O(inf).