I maintain that being able to implement a sorting algorithm from memory is a cheap trick, and has no correlation with programming ability. I've written maybe one sorting routine since leaving college. Being able to pick the correct one for a certain situation is important, sure, but there are battle-tested implementations available for nearly every algorithm in nearly every standard library.

I'd settle for the interviewee understanding big-Oh notation and being able to explain the complexity of an algorithm, given an implementation in a language they understand. If they can do that, it means they have the skill you're really looking for: that they can detect an unnecessarily expensive algorithm. (Isn't that really what the sorting algorithm questions are all about anyway?)