0
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Well, there is Quick Radix Sort where an odd/even split gives a whopping 1-bit head-start. $\endgroup$ – greybeard Dec 6 '19 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.