Here's a full diagnosis of why this is happening:

• \patchcmd{definiendum}{find}{sub} replaces all occurrences of the stringfind with the stringsub in the definition ofdefiniendum. In this case:\ALG@step is called whenever an algorithm moves to the next line, so it has an\addtocounter{ALG@line}{1} in it.
• \ref and\autoref are given as argument the argument of a\label, and produce a hyperlinknot to where the label is, but to where the last "hyper-hook" was set before that\label call. By default, analgorithm environment puts a hook on its title bar, but analgorithmic environment doesn't put a hook on its lines. Hence, by default, putting labels next to lines hooks them to the correct algorithm, but they all flush up to the preceding title bar instead of hooking to the line.
• Hooks have an ID that must be unique. When two hooks have the same ID, anylabel hooked to the second hook will produce a link to the first hook.
• \stepcounter adds 1 to a counter.\refstepcounter does the same, but italso puts a hook at the current position based on the counter's value,and a reference to this hook will show up in the text as the value of the counter afterwards.
• For sections and subsections, notice that the subsection value resets with each section, yet you can still produce a link to subsection 2.1 even if there is already a subsection 1.1; the hook IDs are different even if the subsection count shows up as .1 in both cases.
• This kind of resetting isnot what happens toALG@line when a newalgorithmic is started. Instead, it is manuallyforced down to 0. The result: it will produce thesame hook IDs as in other algorithms with the same line numbers.

You should replace the\makeatletter ...\makeatother by the following code instead:

\newcounter{algoline}[algorithm]\renewcommand{\thealgoline}{\arabic{algoline}}\makeatletter\patchcmd{\ALG@step}{\addtocounter{ALG@line}{1}}{\stepcounter{ALG@line}\refstepcounter{algoline}}{}{}\newcommand{\algolineautorefname}{line}\makeatother

It treats algorithms like sections and lines like their subsections. That is: the lines seem to reset when moving from one algorithm to the next, but the counter system generates a unique ID for the hook of line 1.1 and line 2.1.

Thanks to @Mew for his analysis.

It seems that I only need to change\theHALG@line properly, which is used byhyperref to generate the unique label.

Now I do not need to change it manually, as the command\@addtoreset is redefined byhyperref so that\theHALG@line is properly defined now.I guess this (clears the counter when a new algorithm starts) won't affect the works ofalgorithmx.

In conclusion, replace the\makeatletter ...\makeatother by the following code will work:

\makeatletter\@addtoreset{ALG@line}{algorithm}\makeatother

• hyperref
• cross-referencing
• algorithms
• algorithmic
• algpseudocode