Problem $2.$ Write an algorithm called mergesort$3$ that sorts an array $S$ of $n$ ints by

dividing the array into three subarrays of approximately $\frac{n}{3}$ ints,

sorting each subarray using recursion, and

merging the three sorted subarrays.

A few notes: this algorithm will be very similar to mergesort $($page $59),$ except that we are splitting

the array into three subarrays. The algorithm's heading should look like this:

void mergesort$3(intn,$ int $S[])$

You may assume that you already have an algorithm

void merge$($ int $h,$ int $m,$ int $t,$ const int $U[],$ const int $V[],$ const int $W[],$ int $S[])$

that merges an array $U$ of size $h,$ an array $V$ of size $m,$ and an array $W$ of size $t$ into the sorted array

$S.$ So you don't have to write merge, you just need to call it within your mergesort $3$ algorithm.

Look at picture for better reference.