Exercise 2.1.2

Rewrite the Insertion-Sort procedure to sort into nonincreasing instead of nondecreasing order.

The only thing we need to do, is flip the comparison:

for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] < key
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = key