A particularly inefficient way to sort a given list of integers consists of generating a random permutation of it and check if such permutation contains the elements correctly sorted. That is the so called bogosort algorithm, performing asymptotically (e−1)·n! integer comparisons and (n−1)·n! swaps in average. This kind of algorithm however has several problems. First, it requires a random generator. Then, the best case runtime is very low, just n−1 integer comparisons and no swaps if the given list is already sorted. Finally, the worst case run time is unbounded.
A variation of bogosort that liminates randomness consists of generating all n! permutations of the given list and then search for the one that contains the elements correctly sorted. This keeps the average run time in Ω(n!) integer comparisons, but still produces a low n−1 number of comparison in the best case.
In order to keep the best case run time high, we will change the strategy to find the correctly sorted permutation. Instead of performing a linear search on the list of permutations, we will sort all n! permutations in lexicographical order, and return the first one of them.
The sorting of the list of integer lists can be performed with any standard algorithm such as bubblesort, which runs in Θ(n²) time. The lexicographical order of integer lists is defined so that L1 < L2 precisely when the first index k ∈ [1,...,n] for which they differ verifies L1[k] < L2[k]. So, comparing two integers lists requires at least one integer comparison, and the total time (number of integer comparisons) required to sort n! permutations of n elements in lexicographical order using bubblesort will be Ω((n!)²).
Now, replace bubblesort with another instance of the algorithm just described, i.e., instead of using bubblesort to sort the n! permutations of the original list of n integers, generate the (n!)! permutations of the list of n! permutations, and then sort lexicographically the list of permutations of permutations. The first element will be a list of permutations of integers lists, and the first element of it will be the original list of n integers sorted in increasing order. The number of integer comparisons performed will now be Ω(((n!)!)²).
We finally answer the question of how inefficient a sort algorithm can be.
To do so we define the following sort algorithm, that takes a list of integers L, and an increasing computable function f: ℕ→ℕ as its arguments.
Our algorithm calls multilevelsort(L, k) with the parameters of L and k = f(length(L)).
For k=0, multilevelsort just performs bubblesort on L. For k > 0, multilevelsort performs k recursive selfcalls before using bubblesort. Its run time is Ω(((...(n!)!...!)!)²) = Ω((n)!^(k)).
Therefore, the runtime of worstsort, that takes f, is Ω((n!^(f(n))²), showing that a sort algorithm can be made as inefficient as we wish, with its runtime growing at least as fast as any growing computable function.
Listen to this song and this playlist