For what it's worth, I think it's totally reasonable to ask a software engineer candidate to implement a binary sort, even if the candidate has to derive the particulars of the algorithm from first principles. If the candidate can't implement something as well-understood as a binary sort, how are they going to perform when given a totally novel problem that no one has ever solved before?

If anything, the problem with that as an interview question is that it is too obvious and common, and will not do a good job distinguishing between a strong candidate and someone who crammed for the interview and happened to practice that particular problem.