4 ms·

> Bins would have an average occupancy of 1, so it didn't matter what sort you used. That's not quite right, though - you only care about the average occupancy

by a1369209993 3y ago

> Bins would have an average occupancy of 1, so it didn't matter what sort you used. That's not quite right, though - you only care about the average occupancy if your sorting algorithm is O(b) for b elements. If you're using a O(b^2) sort, you actually care about the root-mean-square occupancy (or in general just the average runtime, or just the total runtime since you'll multiply the average by the number of bins anyway). The k-bin approach is definitely much faster than O(k log k), but I'm fairly sure it's slightly slower than truely linear, asymptotically, since the runtime will be something like 1+0+4+1 in typical cases, where linear would have to be 1+0+2+1. Edit: on some cursory Monte Carlo testing, the sum of squares of occupancies actually seems to still converge on a constant factor (of two) times the sum of plain/linear occupancies, which I was not expecting but does make the above point rather moot. (Also, the sum of cubed occupancies seems to converge on a factor of five, which seems downright bizzare.) (Tangential edit: The factors seem to be 1 2 5 15 52±2 200±20, which might be https://oeis.org/A000110 https://oeis.org/A000110, though none of the interpretations there seem obviously related.)

Syzygies 3y ago
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.

Syzygies 3y ago

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.