I am willing to write this.

 

I looked at both the Emacs and the Elisp manuals and the only change necessary would be in the elisp manual where the full code for sort-lines is shown, so that would be a simple replace.

See below. 

For clarity, the original behavior of sort-lines is what the patch restores.  The backward-incompatibility to which you refer is then just an implementation error that occurred when switching over to the overlay implementation of outlines as there was never any documentation that I can see that suggested any behavior change.  There certainly could be better documentation as to whether a 'line' refers to a visible line, an invisible line or both but many functions do not delineate this.  A major reason for making lines invisible is so that they are not treated as regular lines when functions are applied to buffer text.  Thus, sort-lines should by default operate on visible lines.  It could be extended or another function could be written to operate on invisible lines as well, e.g. sort-invisible-lines and an alias could be made to sort-lines to be called sort-visible-lines.  All of this in the future.  The only thing I am suggesting for right now is to restore the original behavior.  Note that if all lines are visible, the patch codes works as well.  The issue is that when lines are invisible the current code in Emacs does not work in a very useful way.

Bob