Rewrite the \(\textsc {Insertion-Sort}\) procedure to sort into non-increasing instead of non-decreasing order.
We just need to reverse the comparison of \(A[i]\) and \(key\) in line 5 as follows…
$$\textsc{Insertion-Sort}(A)$$$$\begin{aligned}
1& \quad \textbf{for }\,j\,=\,2\textbf{ to }\,A.length \\
2& \quad \qquad key\,=\,A[j] \\
3& \quad \qquad \textbf{/\!/} \text{ Insert}\,\text{ A[j]}\,\text{ into}\,\text{ the}\,\text{ sorted}\,\text{ sequence}\,\text{ A[1}\,..\text{ j-1]}\, \\
4& \quad \qquad i\,=\,j\,-\,1 \\
5& \quad \qquad \textbf{while }\,i\,>\,0\textbf{ and }\,A[i]\,<\,key \\
6& \quad \qquad \qquad A[i + 1]\,=\,A[i] \\
7& \quad \qquad \qquad i\,=\,i\,-\,1 \\
8& \quad \qquad A[i + 1]\,=\,key \\
\end{aligned}$$