3 ms·

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

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.

a1369209993 3y ago
> There's a fixed, rapidly vanishing probability distribution on bin occupancies, Pretty much; my mistake was underestimating just how rapidly it vanishes. In actuality any sorting algorithm that isn't pathologically horrible garbage like bogosort will work fine, because it runs on meaningful numbers of elements so rarely that it doesn't matter (and I'm not totally sure bogosort is garbage enough). > where the constants in front of fancy sorts took them out of the running. For beating O(k log k), the constants don't actually matter, since they just increase the constant factor inside your O(k) runtime. It's just that apparently, the asymptotics don't matter much either for that.