2.2 In-Place Partitioning (15 pts) One of the key steps in each recursive call to quicksort is the partitioning step. This involves solving the following problem: Given an array A and a pivot p, rearrange elements in A to get A - [A1, A2, A3] where A1 consists of elements less than p, A2 consists of elements equal to p, and A3 consists of elements greater than p. Let's assume for now that the array has all distinct elements, so we don't have to worry about A2. A straightforward way to solve this problem is to use another array of size n to rearrange the elements. Below is a better way to do the partitioning in-place Partition (A[1,... , n], k) Input: An array A[1, ..., n] of n elements and an index k that contains the pivot element Output: The method rearranges the array A correctly and returns the final index of the pivot element If n-l return A If n-2, swap (A1], A[2]) (if needed) to sort the array and return A Else swap (A[k],A[[n]) Set p-A[n] Set i-1, j-n-1 while (i p and A[j] p and Alj] > p j- Else If A[i]