An example

The following example demonstrates the use of the pseudocode environment to describe a complete algorithm, the familiar ``mergesort'' algorithm. The L^ATEX input

\renewcommand{\thepseudonum}{\roman{pseudonum}}
\begin{pseudocode}{MergeSort}{n,X}
\label{MergeSort}
\COMMENT{Sort the array $X$ of length $n$}\\
\IF n=2 \THEN
\BEGIN
  \IF X[0]>X[1] \THEN
  \BEGIN
    T \GETS X[0]\\
    X[0]\GETS X[1]\\
    X[1]\GETS T
  \END
\END
\ELSEIF n>2 \THEN
\BEGIN
  m\GETS \lfloor n/2 \rfloor\\
  \FOR i\GETS 0 \TO m-1 \DO A[i] \GETS X[i]\\
  \FOR i\GETS m \TO n-1 \DO B[i] \GETS X[i]\\
  \COMMENT{Now sort the subarrays $A$ and $B$}\\
  \CALL{MergeSort}{m,A}\\
  \CALL{MergeSort}{n-m,B}\\
  i\GETS 0\\
  j\GETS 0\\
  \FOR k \GETS 0 \TO n-1 \DO
  \BEGIN
    \IF A[i] \leq B[j] \THEN
    \BEGIN
       X[k]\GETS A[i] \STMTNUM{1in}{st.1}\\
       i\GETS i+1
    \END
    \ELSE
    \BEGIN
       X[k]\GETS B[j] \STMTNUM{1.03in}{st.2}\\
       j\GETS j+1
    \END
  \END
\END
\end{pseudocode}

produces the following output:

 

The counter pseudonum keeps track of the statement numbers. The style of the counter values can be changed using the method described in Section 6.3 of [3]. For example, we used the command

\renewcommand{\thepseudonum}{\roman{pseudonum}}

in our example so that statements were numbered with lowercase Roman numerals. We also assigned a label to the algorithm using the \label{} command that is described in Section 4.2 of [3]. Finally, by trial and error, we determined spacing so that the statement numbers would be vertically aligned.

We now give an example of how the numbered statements in the above algorithm can be referenced in a L^ATEXdocument. The commands

On lines (\ref{st.1}) and (\ref{st.2}) of Algorithm 
\ref{MergeSort}, we determine the $k$th element of the 
sorted array.

produce the following output:

On lines (i) and (ii) of Algorithm 3.1, we determine the kth element of the sorted array.