What is the time complexity of the sleep sort?
Given this sort algorithm how do you express its time complexity?
Originally presented here (partial archive).
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait
example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7
Answer
O(max(input)+n)
The complexity just appears awkward to express because most sorting algorithms are data agnostic. Their time scales with the amount of data, not the data itself.
FWIW, as pointed out here, this is not a reliable algorithm for sorting data.