One should know that it is the timer scheduler of the kernel which ends up doing the sorting. With Linux, this is probably a red-black tree[1], so performance of sleep sort (when it works) is O(n *log(n)).

[1] https://www.kernel.org/doc/Documentation/timers/hrtimers.txt