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 }A[j]\text { into }\text { the }\text { sorted }\text { sequence }A[1\text { .. }j-1] \\4& \quad \qquad i=j-1 \\5& \quad \qquad \textbf {while }i>0\text { 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}$$