[1wd]

O(n+n * log(w/log(n)) )

Wouldn't this decrease again for large enough n, and even go negative after n=2^(w * 2)?

[dan-robertson]

The algorithm is to switch to a counting sort when w <= log n, ie n >= 2^w, so more properly the complexity is written:

  O(n+max(0,log(w/log n)))

[karpierz]

The recursion assumes that log(n) > w; if log(n) <= w, then you're in the base case and it's O(n).

[rocqua]

Not sure whether it applies here, but _if_ n is the number of unique values, you are limited here by the fact that there are only 2^w unique integers. Hence n < 2^w

[ben-schaaf]

Not sure what's going on here, but that does indeed seem to be the case: https://www.wolframalpha.com/input/?i=x%2Bx+*+log%282%2Flog%...