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

>>16
That's good, except it should first check if the array is sorted already and if it is, unsort it.
To extend the concept, make a program that searches the memory of currently active processes and automatically detects any sorted arrays and messes them up on sight.