Cormen Edition 3 Exercise 2.1 Question 2 (Page No. 22)

Question

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

Answer 1

Insertion-Sort(A,n)  //A[1....n]

   For j <- 2 to n

        do Key <- A[j]

           i <-  j-1

        while(i>0 and A[i] < Key) 

             do A[i+1] <- A[i]

                i <- i-1

        A[i+1] <- Key