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