Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non-decreasing order.

We just need to reverse the comparison of and in line #5

1
2
3
4
5
6
7
8
for j = 2 to A.length
    key = A[j]
    // Insert A[j] into the sorted sequence A[1..j − 1]
    i = j  1
    while i > 0 and A[i] < key
        A[i + 1] = A[i]
        i = i  1
    A[i + 1] = key
If you have any question or suggestion or you have found any error in this solution, please leave a comment below.