After covering the semi-awful GnomeSort, I decided to dig into papers on sorting algorithms to see if anyone’s ever published something on a completely awful sort algorithm. This led to BogoSort, first published in 1996 in the New Hacker’s Dictionary and then analysed by Hermann Gruber, Markus Holzer and Oliver Ruepp for some reason at some point later in time.
The basis of bogosort is to randomly swap elements in your array until they become sorted, which required one pass to randomly swap elements and another to verify it was sorted. This give a worst case O time of O(N * N!), though in theory it could run forever. However odds are even with a large number of elements it will eventually finish, after all even if it’s unlikely given enough time you’ll see an end. Even a big bang happens every once and awhile due to randomness.
View original post 69 more words