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

>>2
ruby vm in java, interpreting php which walks FIOC ASTs implementing an x86 emulator running windows 3.1