Which sort algorithm to choose given two specific arrays?
I believe the goal of this question was to get you to say that the information about even or odd can't lead to any significant speedup in runtime. 

Suppose you have an algorithm which works very fast in that case. Then, given any array of integers, you can split it up into an array of even integers and an other of odd integers in linear time. You can then run your super fast algorithm on these arrays to sort your original array super fast as well. Thus, a faster algorithm for this case would lead to a faster algorithm in the general case. So you can safely choose to use whatever sorting algorithm is fastest in the general case (asymptotycally $O(n\log n)$).