Great news, I finally wrote a sorting algorithm that worked for 10/10 of my test cases. Now, I can just plug that number into my unproven statisticle test, and found out how likely it is that my algorithm will work for all inputs.

It does not seem to run extra slow for any input, so it probably won't run slowly on any input in actual use. Besides, even if it did I would have no way of proving what types of inputs it failed on, or if another algorithm would do better.