Design a 3-way merge sort algorithm, which divides the given array into three equal parts, recursively sorts each part, then merges the results. In the main MergeSort3(A,p,r) algorithm, you may assume the existence of an appropriate Merge3(A,p,q1,q2,r) linear-time (Θ(n)) algorithm. Provide the pseudocode for the main algorithm (but not for the Merge3 helper).