Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing order.

The only necessary change is to change the > on line 5 to a <.

INSERTION-SORT(A)

1 for j = 2 to A.length

2     key = A[j]

3     //Insert A[j] into the sorted sequence A[1..j-1].

4     i = j - 1

5     while i > 0 and A[i] < key:

6         A[i+1] = A[i]

7         i = i - 1

8     A[i+1] = key