Normally in merge sort we take an array, split it into two arrays of half the length of the original, sort those recursively, then merge the results together. In this problem you're asked to modify the merge sort to make 3 equally sized recursive calls:.
create 3 arrays of 1/3 the original length,
make recursive calls on all 3, and
merge the 3 (now sorted) arrays together.
Note, the size of A will always be divisible by 3 evenly (i. e. A. length%3==0).
Hint: for an array C and an index i, ((i>=C. length)?C[i]:Integer. MAX_VALUE) will be the value at C[i] if i is inbounds and "infinity" otherwise.
Example:
Given {5,8,3,1,7,2,9,6,4}
the 3 recursive calls would be made on {5,8,3}, {1,7,2}, and {9,6,4}
3 subsequent recursive calls (3 sets of 3) would be made on ({5}, {3}, & {8}), ({1}, {7}, & {2}), and ({9}, {6}, &{4})
3 merges are done to create {3,5,8}, {1,2,7}, and {4,6,9}
these results are then merged back into the original array as {1,2,3,4,5,6,7,8,9}.
Example:
Given {4,7,2}
the 3 recursive calls could be {4},{7},{2}
the resulting merge is {2,4,7}
The signature of your method will be
public static void merge3 Sort(int[] A)