The real point is that, due to distro fragmentation, Linux gives the casual user an inconvenient shared library linkage experience. At the same time the distros are really good as packaging software, which gives us the "one-click install" experience we're so use to. But they do so, at the price of compatibility, so we have the current distro lock-in situation.

Anyway, as an upstream software developer, I see the medal from the side of library linkage: when my program starts, the dynamic linker resolves this big list of symbols that my program contains and finds me matching libraries. You can extend this paradigm to icons, locale, and other support files as well.

So who tells the dynamic linker which symbols to match? Well, the contents of the shared libraries, and these already contain versioned symbols (e.g. this memcpy@1.0 does this, memcpy@1.1 doesnt do that anymore). The easiest solution to the matching problem is static linking. But that's not what we really want, because we may actually want to replace symbols with better versions (due to security fixes, faster implementations, super-set of features, etc).

And who versions symbols? Well, usually the upstream developers of the important libraries do. And they do that somewhat remarkably well already, but it could be better. If your program uses an upstream that doesnt version things, well, bad choice, static linking is probably the best solution here.

So what I would propose, is to move the problem down to a linkage problem, with better consensus between binary creators and upstream authors on how to version symbols. And if my system currently doesnt have a matching symbol installed? Just download it from the distro's well-versioned repositories, maybe not the whole gtk+ library, but a diff of it to another version.

We would then in the end not have a package installer, but a fetcher-of-missing-versioned-symbols-for-a-binary installer. But this model is pretty far fetched, since the current method of compiling code into monolithic shared libraries is much simpler. On the other hand, the linux dynamic linker is already very intelligent, maybe it's time for the large distros to cooperate on this level.

To make it I needed a C++ version with iterators, which I though would be faster. But it is still about 20% slower than stable_sort for the default random input test. It probably also stays the same for other inputs.