Here's a MWE that shows the issue:
Code: Select all
\documentclass{article}
\usepackage{algorithm}
\usepackage{algorithmicx}
\begin{document}
\begin{algorithm}
\begin{algorithmic}[1]
\State foo \Comment{ \parbox[t]{3in}{This is a very long comment, that needs to span several lines, but doesn't need to take up vertical space, as the following lines of code are short, and don't need comments in the margin}}
\State foo
\State foo
\State foo
\State foo
\State foo
\State foo
\end{algorithmic}
\end{algorithm}
\end{document}