I don't see the relevance. The fact that you're asking someone to code a mergesort or a red-black tree tells me that you don't know how to interview, not that interviewing doesn't give you useful information. Candidate #2 sounds like they passed the interview - what did I say that made you think I'd reject them?

Yeah, if you're really bad at interviewing, it's not going to give you good information. I'm not disputing that. Interviewing, as it's done where I work (and everywhere I've interviewed, which admittedly isn't very many places), has been very effective at reducing false positives.