What is the dumbest code ever made that has become famous? by John Byrd
Answer by John Byrd:
That code would be. This bit of code is not famous yet, as it was only invented in 2012, but it’s pretty amazingly brilliantly dumb.
I'm going to tell you a new sorting algorithm, it's called badsort.
To run badsort on three numbers, 3, 2, and 1, you start by generating all permutations of those numbers.
[math][( 3, 1, 2) (3, 2, 1) (2, 1, 3) (2, 3, 1) (1, 2, 3) ( 1, 3, 2 )][/math]
Six permutations. Now, you sort those six permutations using good old fashioned bubblesort. You have six elements, so you compare each element of the list by comparing each element of each element of each list.
After the bubblesort, the permutation at the top of the list is the sorted result [math] (1, 2, 3)[/math], so return it.
Congratulations. You have sorted the original list in [math]O(n!)^2 [/math]time.
But wait. What if you don't use bubblesort in the middle of badsort? What if you use badsort itself, and then use bubblesort after you've badsorted recursively twice?
If you use badsort inside badsort and then bubblesort, the crappiness of the sort is now [math]O((n!)!)^2.[/math]
Of course you are sorting lists of lists at this point, but you know how to do that.
Using this method, you can recursively badsort as deeply as you want, to make the sort just as slow as you want it to be, [math]O((((…..((((((((n!)!)!)!)!)!……)^2.[/math]
And that’s worstsort. Just recurse as many times as you want on badsort and do a bubblesort at the end. This algorithm is much, much worse than any other known sort for a large number of recursions. But it is still guaranteed, eventually, to sort the lists.
There is no computable limit to the inefficiency of worstsort. You can sort until the heat death of the universe, then start a new universe to continue worstsort, and then wait till that universe dies of heat death, and continue on with any finite number of universes.
But if you chose a recursion sufficiently deep, you will still be waiting on worstsort, which is guaranteed to finish sorting in some universe further on.
Also, you will run out of space in the universe to store all those permutations of permutations, so be sure to pick up some parallel universes for external storage.
That's worstsort. It kicks bogosort’s and sleepsort’s and even bogobogosort’s asses in terms of awfulness.