Yes, by Microsoft in 2001. (Strangely, by a non-technical recruiter who wouldn't have known if it were correct or not anyway; apparently he was trying to "gauge my confidence".)

More than once. Also, merge sort, heap sort, and some problem specific variations of these.

quicksort, shellsort, then implement it for parametric type.

I am not even sure what implementing it for a parametric type means... can someone point me to a link?

Parametric type means to take the type as a parameter; parent was probably asked to use Generics in C# or Java or C++ templates.

Ah, ok