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.