1.      

The odd-even mergesort algorithm was developed by K.E. Batcher. It is based on a merge algorithm that merges two sorted halves of a sequence to one completely sorted sequence. In contrast to regular mergesort, this algorithm is not data dependent, i.e. the same comparisons are performed regardless of the actual data. Therefore, odd-even mergesort can be implemented as a sorting network.Links to an external site. The following algorithm merges a sequence whose two halves are sorted to a sorted sequence: Algorithm OddEvenMerge (A, B, C): Input: Two sorted halves of an array, A = [1,2,...,an] and B = [b1, b2bn], and an empty array, C, of size 2n Output: C, containing the elements from A and B in sorted order + Let 01 + [1,3,5,...,an-1] Let 02 Let E1 Let E2 + + [b1b3b5bn-1] [2,4,6,...,an] [b2, b4, b6,..., bn] call OddEvenMerge (01, 02, 0), where 0 = [01, 02, call OddEvenMerge (E1, E2, E), where E = [e1, e2, . 3 On] 3 en] Let C + [01,1,02, 2,...,on, en] //remember C is of length 2n for i + 1 to n do Do a compare-exchange of C[2(1-1)] and C[21] return c Objective To implement the OddEvenMerge algorithm as a sorting algorithm using the mergesort technique, i.e. going from pseudocode to programming code. To understand and learn to apply the concept of the (recursive!) divide-and-conquer algorithm. In our case, we will be implementing this in a way such that we enter in one large array, consisting of two half-length sub-arrays, both of which are already sorted. Tasks Write a Java class named OddEvenMergeSort. Define the following method in the OddEvenMergeSort class, which takes in an integer array arr containing the two sorted halves: public int[] sort (int[] arr) {\ } // Your code here Implement the sort method to sort the given array arr in ascending order (from smallest to largest) using the OddEvenMerge algorithm, as described above. To separate the input array into odd and even arrays (returning 1 array containing these 2 arrays), you may use the following method: public int[][] separateOdd Even (int[] arr) { } // Your code here Implement the oddEvenMerge method to merge the odd and even arrays into a single array using the OddEvenMerge algorithm. This part can be implemented using a helper method as follows: public int[] oddEvenMerge (int[] oddArr, int[] evenArr) { } // Your code here This method should take in two sorted arrays (oddArr, evenArr) and merge them into a single sorted array (output) using the OddEvenMerge algorithm. To compare and exchange elements in the output array, you should use the following method: public int[] compareExchange (int[] input) { // Your code here } Finally, finish the sort method created in step 1 to use the above helper methods to sort the input array. Make sure to call the helper methods in the correct order.