I need the following Java Merge Sort Algorithm modified so that it splits the list into 3 sublists instead of 2. Each sublist should contain (n/3) items. The new algorithm must sort each sublist recursively and merge the three sorted sublists. The original merge sort algorithm has an avg and worst-case performance of O(n log n). What is the new performance of the 3-way merge sort?

import java.util.Arrays; public class MergeSort { public static void main(String[] args) { int[] values = new int[15]; for(int i=0; imin) { int pivot = (min+max)/2; sort(data, min, pivot); sort(data, pivot+1, max); int left = min; int right = pivot+1; int[] merged = new int[max-min+1]; for(int i=0; imax || data[left]