3 ms·
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)))
by dan-robertson 6y ago
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)))