> In a nutshell the prior version was a polymorphic function pointer that varied by the sort type.
> (*sort_ptr)(data);
> No compiler can inline this, no matter how aggressively you turn up the optimizations.
LTO can inline these just fine, provided the object files contain the necessary info (i.e. the IR or assembly from static archives, which is how -flto works for clang and GCC). I even tested this using a copy[1] of OpenBSD's qsort implementation a few weeks ago, verifying that both the sort algorithm itself as well as the comparator were inlined, just as would happen with C++ template'd vector sorting.
[1] I had to use a copy of qsort because the compiled libc qsort lacks the accompanying info necessary for LTO. But in theory libc and shared libraries in general could ship critical routines with the necessary metadata required for LTO optimizations. (IOW, a cross between a dynamic and static library.) Fundamentally this is just a toolchain issue, not a language issue. AFAIU, Rust code works much the same way, and its comparator functions tend to be inlined because Rust effectively compiles using LTO (and heavily relies on these implicit optimizations), except that because all Rust code is compiled statically, the necessary IR is always available. The same would be true of Go, but the Go compiler doesn't optimize as heavily. FWIW, AFAIU the C++ standard doesn't guarantee a templated sort comparator would get inlined, either, even if you're using a lambda. But this is optimization is extremely likely when the sort algorithm itself is template-expanded and the comparator is simple--as almost all would be.