> There's a fixed, rapidly vanishing probability distribution on bin occupancies, Pretty much; my mistake was underestimating just how rapidly it vanishes. In

> 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.