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

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

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

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