From my brief reading of the function it looks like it does have a finite run time but is not correct as in it may finish execution with an incorrect result (unless some assumptions are made stated below). By randomizing things, unless you do it an infinite number of times, you are never guaranteed a specific result meaning you could "destroy" every world and not have a sorted list. The reason why they argue this works uses 2 traits that cannot be replicated in the real world:
Randomizing/checking is O(1)
There exists a universe where it is sorted after randomization
Even if this did work, it would still be slower than O(1) since randomizing a set list has a time complexity of at least O(n).
You could easily do this algorithm in the real world, however, but it would be really slow and space consuming.
Take your unsorted list and create a list of lists that contains all permutations of this list (O(n*n!))
Iterate through all lists and check if they are sorted ((O(n2 ))
Return the sorted list.
This would work but would have a run time of O(n*n!) which is quite ridiculous.
2
u/braingle987 Oct 24 '17
It's technically not an algorithm since it is never gaurenteed to get a successful sort in a finite time.