What is the time complexity of the sleep sort?

Question

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 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.

Answer 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).