sleep_sort is incorrect

[workingjubilee]

It has two problems:

1. thread::sleep does not guarantee wakeup after the sleep time has elapsed. This is impossible to fix... but I must admit, it will tend to work fairly often.
2. More fixable yet more egregious is that spawning threads takes a nonzero amount of time! Even if it only consumes a few microseconds, this means that takes less than 1000 items being sorted to throw off things by an entire millisecond, which is disastrous to this sorting scheme. In reality, it takes far less, as your tests don't pass on craterbot. All threads should do something like spin on an AtomicBool so that they only commence sleeping when they are all spawned.

[Voultapher]

Another issue of the current impl is the Mutex::lock call, which serializes the execution into some unspecified order, creating yet another point of failure.

Spinning on an AtomicBool as latch mechanism comes with its own issues, especially if there are more threads than logical cores on a machine, the OS has to interrupt the threads and give each a time-slice to work with, spinning will make this situation worse than just sleeping, plus energy usage will skyrocket for the spawning phase. Arguably that same issue already exists with inputs with many equal elements, but this will make it worse. However, not spinning also yields broken behavior.

I'm not sure there is a way to remedy the situation in a way that makes the tests fail without false positives. Even bumping sleep-time and test input separation is bound to fail at some point. I would either mark the tests as #[ignore = "unreliable"] or add a statistical re-try loop around it in the tests that checks that it fails something like 8 out of 10 attempts.

[Chromfalke]

I have bumped the time to sleep from milliseconds to seconds to make the algorithm a bit more reliable when trying to sort larger arrays and to account for small delays in the sleeping behavior of the threads.

Apart from that I have simply added infinite loops to all tests except the one sorting the empty vector. These loops will only terminate once the elements have succesfully been sorted. Since it is Sleep Sort we are talking about here I feel like running multiple iterations until the desired result is produced isn't much of an issue and actually kind of fits in.