2. Sorting & searching

(a) Give a recursive algorithm for insertion sort. Also, output the number of inversions in the input array.

(b) Find the missing number. You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in the list. One of the integers is missing in the list. Give an algorithm to find the missing integer. Give the worst case time complexity for your algorithm. Can you improve it? Example Input: 1,2,5,3,6,4,8. Output: 7.

(c) Given an array of 10,00,000 pixel color values, each of which is an integer in the range [0,255]. Which sorting algorithm is preferable for sorting them?