So, the minimum running time for this would be O(1), but can one estimate the maximum? I don't see how, but maybe I'm missing something.
Edit: wow nevermind, I just read the paper linked to bozo sort in wikipedia. They conjecture that it's O(n!) whereas bogosort is Omega(n*n!). Wow, that's surprising!