Radu Gigore tweeted "People are obsessed with finding the best algorithms. What about the worst?" So here's a Christmas gift that keeps giving, the slowest of sorting algorithms.
Before you read on, try to think of the slowest sorting algorithm. No fair spinning its wheels, sleeping or doing unrelated tasks. It should always make progress towards sorting.
Here are some examples, in particular bogosort that generates all permutations until it finds a sorted one. Takes n! time on average.
But we can do much worse. The following redicusort algorithm I got from Stuart Kurtz back in the 90's.
Generate all permutations and then sort those permutations. The sort of the original permutation will be first on the list.
The running time depends on the sorting algorithm you use after generating the permutations.
If you use bubblesort you get a (n!)2 time algorithm.
If you use bogosort you get a (n!)! bound.
What if you just call redicusort recursively? The algorithm will never end. If you want to guarantee termination you need to bound the depth of the recursion. Choose something like an Ackermann function to get a sorting algorithm that always makes progress but not primitively recursive. In general you can get a sorting algorithm that takes longer than any fixed computable function.