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?