Design a divide-and-conquer algorithm that will find the missing string in Θ(n) time. Youcan assume that we can utilize thePartitionalgorithm that is used byQuickSort, bymodifying it to compare strings instead of comparing numbers (you do not need to show howto do the modification). Write the pseudo-code of your algorithm and explain how it works.(Hint: You can select the pivot used forPartitionalgorithm in an informed manner thatguarantees the resultant subarrays to be of nearly equal size.)