BogoStalinSort

[programminghoch10]

I propose addition of a new sorting algorithm which combines the best features of both stalinsort and bogosort.

The algorithm is fairly simple:
Just randomly remove elements until the array is in order.

Complexity ranges from O(n) to O(n²)

Hope this will make the world a better place!

[adri326]

Alternatively:

1. Iterate through the array to verify that it is in order. If is is, exit the loop
2. Pick two random indices i,j ∈ [0; n[; i < j
3. If L[i] <= L[j], go back to step 2
4. If L[i] > L[j], remove L[j]
5. Go back to step 1

Best-case complexity is O(n), worst-case is O(n³) (n² random picks per iteration, n iterations, step 1 is dwarved by steps 2 and 3).