# Which sort algorithm to choose given two specific arrays?

Interview question:

Given array A which contains only odd numbers and array B which contains only even numbers, explain which sort algorithm would you choose.

I said merge sort. I thought that given two lists both of which are sorted (which I assumed) I can just merge them i.e use the merge part of merge sort. I was then asked if the numbers were not even or odd would I have chosen merge sort still? Then I was asked if both arrays were not sorted i.e. A contain even numbers (not sorted) and B contain odd numbers (not sorted) which algorithm will I use. I said in practice quicksort typically performs better. I wanted to ask if the length of the arrays is not too big because then bucket sort might do but given his insistence on odd and even integer arrays I did not go for bucket sort (I was afraid I was mentioning all the algorithms). Does anyone know which algorithm might the interviewer be looking for?

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)$$).