make a linear pass through the data, if they are in order quit, otherwise swap two random entries and repeat
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!