2. Show how quick sort can be made to run in O(n log n) time in the worst case assuming that all elements are distinct. Provide a pseudo-code for the modified version of quick sort and show that it runs in O(n log n) time (which means it is also (n log n)). The quick sort algorithm is given below. PARTITION(A, p.r) 1 x = A[r] 2 i = p-1 3 for j = p to r - 1 4 if A[j] x 5 i=i+1 6 exchange A[i] with A[j] 7 exchange A[i + 1] with A[r] 8 return i +1 QUICKSORT(A, p,r) 1 if p