Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array \(A = \langle 31, 41, 59, 26, 41, 58 \rangle\).

\[\newcommand\T{\Rule{0pt}{1em}{.3em}} \begin{array}{|c|c|c|c|c|c|c|} \hline \textrm{Step} & \textrm{1} & \textrm{2} & \textrm{3} & \textrm{4} & \textrm{5} & \textrm{6} \\\hline \T & 31 \T & 41 \T & 59 \T & 26 \T & 41 \T & 58 \\\hline 1 \\\hline \T & \textbf{31} \T & \underline{\textbf{41}} \T & 59 \T & 26 \T & 41 \T & 58 \\\hline 2 \\\hline \T & \textbf{31} \T & \textbf{41} \T & \underline{\textbf{59}} \T & 26 \T & 41 \T & 58 \\\hline 3 \T & ← \T & ← \T & ← \T & ← \\\hline \T & \underline{\textbf{26}} \T & \textbf{31} \T & \textbf{41} \T & \textbf{59} \T & 41 \T & 58 \\\hline 4 \T & \T & \T & ← \T & ← \T & ← \\\hline \T & \textbf{26} \T & \textbf{31} \T & \underline{\textbf{41}} \T & \textbf{41} \T & \textbf{59} \T & 58 \\\hline 5 \T & \T & \T & \T & \T & ← \T & ← \\\hline \T & \textbf{26} \T & \textbf{31} \T & \textbf{41} \T & \textbf{41} \T & \underline{\textbf{58}} \T & \textbf{59} \\\hline \end{array}\]

The idea here is that the step rows are indicating what action occurs in the row beneath them. Left-pointing arrows demonstrate that an underlined number has been moved to a new position, and by following these arrows you can map an array element from its original position to its new destination.