When it comes to solving simple polynomials with complex coefficients and complex roots, we can use explicit formulae. For example, the roots for polynomial $z^2-c$ are the list $(\sqrt c,-\sqrt c)$. A small perturbation in the coefficients will result in a small perturbation of the roots, but the list will not be permuted.
For polynomials of higher degree we will use some kind of numerical procedure that gives us a list of roots. But running the numerical procedure on the same polynomial a second time may give us the same roots in a different order (because it may have used randomness in selecting the starting point of an iteration). And even if that's not the case, there is no guarantee that perturbing the polynomial slightly will yield the perturbed roots in the same order as the roots of the original.
For example, a numerical solver might give the roots of $z^2-c$ as $(\operatorname N(\sqrt c),-\operatorname N(\sqrt c))$ and the roots of $z^2-(c+\epsilon)$ as $(-\operatorname N(\sqrt {c+\epsilon},\operatorname N(\sqrt {c+\epsilon}))$, where $\operatorname N()$ is a numerical approximation.
Are there numerical root finders that preserve root order as well as formula based solvers? (There are some complexities that are discussed in the comments ... it impossible for roots to vary continuously with coefficients everywhere - even formula based solvers will have branch cuts)
The polynomials I'm interested in are of small degree - less than 10. And I would be happiest if the answer also pointed to a reliable open source implementation.
This is not a complete answer, merely a comment turned into an answer to provide potentially useful keywords and references.
Your question reminds me of work a former colleague of mine (S. Kranich) had been doing. An epsilon-delta bound for plane algebraic curves and its use for certified homotopy continuation of systems of plane algebraic curves is the best reference I can find for that at the moment. It would relate separation of roots to permitted perturbation, I believe. As some comments pointed out, there are definitely some evil polynomials where that relationship is really poor, and even a tiny change in coefficients would lead to a massive change in roots, defeating the approach.
Perhaps the “homotopy continuation” mentioned in that title is the kind of concept you meant to ask for? As I understand it, the idea is that you aim to track roots along a path from the original situation to a somewhat perturbed one. The above paper will tell you how big you may make the individual steps along this path if you want to be certain that matching roots by minimal distance will map things “correctly”, or more specifically map them the way a continuous movement with infinitely small steps would map them. Of course the path has to avoid singular situations / multiple roots if it is to have any chance at success.
I'm not sure if the above paper takes numeric issues into account. If you have a theoretic guarantee about roots having a certain guaranteed separation, then the fact that any numeric approach will only find approximations of the actual roots might water down the benefit. You might even reach a situation where the either the guaranteed situation is smaller than the expected numerical rounding error, or the step size along the path smaller than the unit in the last place of your perturbation variable.