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

I see what OP's master plan is here.

#1) Develop top selling product
#2) Wait until the product is on 90% of all usable machines
#3) Release update including the following code:
     Add program to startup queue
     Disable any functionality allowing users to end the program
     Start 20 threads, each doing:
     Create int array of size 999,999,999
     Sort as slow as possible using what is essentially bogosort.
     ???
     Profit.

Genius.