3. There are some situations where we are asked to sort data that is almost sorted. A k- sorted array contains no element that is more than k positions from its position in the properly sorted array. For the questions below, A is a k-sorted array with k A[j], then the pair (i,j) is called an inversion of A. What permutation of the array {1, 2, ..., n} has the most inversions? How many does it have? b. Give the list of [2,5, 1, 6, 3, 4], what is its number of inversions? What is the number of inversions in its reverse? c. Show that, if A is k-sorted, Insertion-Sort runs in time O(nk). Hint: First, show that INSERTION-SORT(A) runs in time O(n+I), where I is the number of inversions in A. d. What are the runtimes of Merge-Sort and Quicksort on a k-sorted array A? Explain your answers. e. (extra credit) Devise an algorithm that performs better than the above algorithms for sorting a k-sorted array