Reminds me of bogosort.
Bogosort is theoretically worse than worstsort, as it might take infinite time. Theoretically.
That’s pretty cool, I love a good worst-of-class attempt (:
But I feel like it’s cheating to keep going once you have produced the correctly-sorted output, and if I’m understanding the explanation right, both solutions do that.
If I understand correctly, it produces all permutations, sorts the permutations lexicographically, and selects the first, which is the most (and therefore fully) sorted one. So it’s not cheating quite in the way you state, because even once it generates the solution, it hasn’t decided it’s the solution.
You could, of course, optimize it by checking if each permutation is sorted as it is generated, and returning as soon as one is. This would still be disasterously slow, but not to the same degree. It would be O(n!) worst case, I suppose, unless I’m missing something.
If the hype about quantum computing in the popular media is to be believed, this algo should be very impressive on a quantum computer ;-p
Worse than sleepsort?
As noted, it makes “progress” at every step.