I've added support for functors and verified it with my keyplusdatasample.c, available from http://sourceforge.net/project/showfiles.php?group_id=229739(spreadsort project). I've also attached the updated integer_sort source. Some design decision notes, which I'd welcome comments on: I'm using pointers to iterate over the bins where I can safely do so (everywhere but recursion). For some pointer values, the bins pointer can be offset by subtracting div_min from it ahead of using it for bin lookups. This shows a noticeable speed improvement (around 2%), but requires checking whether this offset is safe to do, is a hack, and requires an if/else with largely duplicate code. My conclusion is that such a hack is not appropriate for Boost code. One disadvantage I found with the 3-way swap is that it requires a public default constructor data_type() to be efficient. If I code it so that it only uses a copy constructor (by moving the creation of tmp inside the if and else, and thus making most of the code dependent upon the conditional check), it is substantially slower. Some object models deliberately eliminate the public default constructor. To stay more general, should I use the conventional 2-way swap approach, even though it is slightly (around 1%) slower? I'm only using constructs that compile on my old g++ compiler. That means I can't use some of the newer additions to the standard, but I'm doing this in the interest of being able to compile on as many systems as possible. After all my optimizations, the impact of pointers vs. random access iterators has increased as a percentage of runtime (it's over 10% now). I'd be interested to hear if this issue is visible on other systems, or just mine, and other suggestions for what might be the problem. I tried an earlier suggestion of a compiler option, and it had no speed impact, though that might be because my compiler treats that option differently. I'll start working on float_sort now.