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.