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

Solution 1:

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.

Solution 2:

One point which nobody seems to have addressed is how those sleeps are implemented. Ultimately they end up in a scheduler somewhere, and the operational complexity will depend on the scheduling algorithm used. For example, if the sleeps are put as events in a priority queue you will likely end up with something equivalent to heapsort, with complexity O(n log n). A naive scheduling algorithm might result in O(n^2).

Solution 3:

I think paxdiablo is nearest, but not for the right reason. Time complexity ignores issues on real hardware such as cache sizes, memory limits and in this case the limited number of processes and the operation of the scheduler.

Based on the Wikipedia page for Time complexity I'd say the answer is that you can't determine the runtime complexity because if it is defined as:

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform. Thus the amount of time taken and the number of elementary operations performed by the algorithm differ by at most a constant factor.

Then we can't talk about the runtime complexity of this algorithm because time which the elementary operations take is so vastly different, that the time taken would differ by more than a constant factor.

Solution 4:

Both the time complexity and the process complexity of that algorithm are O(braindead):

• With a sufficiently large value in the data set, you'll be waiting for an answer until the sun explodes (2⁶⁴ seconds is a little over half a trillion years).
• With a sufficiently large data set size, you'll (a) hit your process limit; and (b) find that early sleeps will finish before the latter ones begin, meaning the set (2,9,9,9,9,9,...,9,9,1) will not sort the 1 and 2 correctly.

Time complexity is irrelevant in this case. You can't get any less optimised than "wrong". It's okay to use complexity analysis to compare algorithms as the data set size changes, but not when the algorithms are ludicrous in the first place :-)