There's a fixed, rapidly vanishing probability distribution on bin occupancies, which evaluates to a constant per bin when one applies a sorting algorithm. One gets linear algorithms with different constants, depending on the sorting algorithm. You're thinking "deep end of the pool" worrying about b log b versus b^2. I was in the "shallow end of the pool" where the constants in front of fancy sorts took them out of the running.

Like I said about Strassen and matrix multiplication. Great algorithm, but it takes a while to kick in for the lead.