In algorithms papers, how common is it to reference accepted software patches based on the algorithm presented in the paper? Is it appropriate to even mention it?
Yes, it is common and fairly reasonable.
So say you've implemented a new method for X. And you submitted it as a PR on say github, as a new feature for "SuperXdoerLibrary", and it was accepted. Then you would, say something at the end of the Section where you describe your algorithm something like:
This method for doing X is now available in SuperXdoerLibrary (V1.23)1.
And then in a footnote put a link to the SuperXdoerLibrary website, or github page. And probably also put a link on your website
It is very common to refer to what implementations of your algorithm referred to in your paper. And a "good thing".
As to if it is a stand alone implementation, or as a component in a larger library, I don't think it matters. I would in-fact suggest it is even better if it is in a larger library as that will generally mean it is in a more usable state.