Rewrite the INSERTION-SORT procedure to sort into monotonically decreasing instead of monotonically increasing order.
A monotonically decreasing order means starting from the highest element to the lowest: 23,22,21,20
The monotonically increasing order for insertion sort is:
INSERTION-SORT (A, n)
for i = 2 to n
key = A[i]
j = i - 1
while j > 0 AND A[j] > key
A[j+1] = A[j]
j = j - 1
A[j + 1] = key
The monotonically decreasing order would be:
INSERTION-SORT (A, n)
for i = n - 1 to 1
key = A[i]
j = i + 1
while j < n AND A[j] < key
A[j-1] = A[j]
j = j + 1
A[j - 1] = key