The question is plain wrong and i think is a trick question. You cannot have an array of 3 different types. Array can only be of a single type. If for some weird reason the interviewer asks you to assume such an array exists, then the first thing needed is Comparison routine or criteria i.e. rules to compare two elements to determine if one is smaller or larger

Interviewee wanted to here solution to Dutch National Flag problem. See http://en.wikipedia.org/wiki/Dutch_national_flag_problem I didn't know about it at that time.

Use counting sort for example.

There is a clever O(n) in-place sorting algorithm for this.