Modify the merge sort algorithm so that, instead of sorting an array, it rearranges places all even elements before the odd ones. For example, the array [1, 4, 9, 16, 25] becomes [4, 16, 1, 9, 25]. Use the same recursion where an array is split in two, each half is rearranged, and the two halves are merged together. However, the merge method needs to be changed to merge two arrays, each of which has the even elements before the odd ones, into one larger array with the same property. MergeSorter.java 1 public class MergeSorter 2 { 3 private int[] a; 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 /** */ public MergeSorter (int[] anArray) { } Constructs a merge sorter. @param anArray the array to sort a = anArray; */ public void evenFirst() { } Places the even elements before the odd ones. } /** if (a.length <= 1) return; int[] first = new int [a. length / 2]; int[] second = new int[a.length - first.length]; // Copy the first half of a into first, the second half into second for (int i = 0; i < first.length; i++) { first[i] = a[i]; } for (int i = 0; i < second. length; i++) { second [i] = a[first.length + i]; } MergeSorter first Sorter = new MergeSorter (first); MergeSorter secondSorter = new MergeSorter (second); firstSorter.evenFirst(); secondSorter.evenFirst(); merge (first, second); Merges two arrays into the array managed by this merge sorter. @param first the first array which has the even elements before the odd ones @param second the second array which has the even elements before the odd ones */ private void merge(int[] first, int[] second) { } // this method is used to check your work public static int [] check(int [] a) { MergeSorter sorter = new MergeSorter (a); sorter.evenFirst(); return a; // TODO