Yeah, so long as you have something else that can quickly verify that a list is sorted, just keep applying this "quick coin toss sort" until you get a sorted list.

If a ML algorithm with a 90% success rate and a "sanity checker" might be much easier to implement than a ML algorithm with a 100% success rate.