Consider the below quickSort(A) function. This function is a little bit different from the quick sort in the class. It calls threePartition function, which partitions a given array into 3 partitions, instead of 2 partitions.

The function threePartition first chooses the last element of the array as a pivot. Then, the first partition contains all elements less than the pivot, the second partition contains all elements equal to the pivot, and the third partition contains all elements greater than the pivot. In addition, the function returns a pair of integers: the first and last indices of the second partition. (Note that the second partition includes the pivot, so cannot be empty.)

Complete the threePartition function so that quickSort(A) correctly returns a sorted array for A. Do NOT modify the function, quickSort(A). You should complete only threePartition(A) function, so that quickSort(A) function works correctly.

def quickSort(A): if len(A) < 2: 

 return A i, j = threePartition(A) return quickSort(A[:i]) + A[i:j+1] + quickSort(A[j+1:]) 

def threePartition(A): n = len(A) 

 pivot = A[n - 1] # choose the last element as a pivot i, j = 0, 0 

 ### Write Your Code Here ### ### This function should return a pair of integers, (i, j), where 

 ### i: the first index of the second partition 

 ### j: the last index of the second partition 

return i, j

# The following should return [1, 1, 2, 2, 3, 4, 4] quickSort([1, 2, 4, 1, 2, 4, 3])