Is the sum of two even numbers even or odd? How about two odd numbers? One odd number and one even number?
If there is an even number of odd numbers, the sum will be even and vice versa.
Create an integer array to store all the even numbers in nums and another array to store all the odd numbers in nums. Sort both arrays.