All you're doing is optimizing for developers who can create sorting algorithms. If you're a company that specializes in developing new, groundbreaking sorting algorithms, that might make sense. But if you're a company that specializes in, say, B2B software, it doesn't make any sense at all. If one of your developers needs to sort something, they'll just use whatever's available in the libraries or frameworks or languages your company uses.
It might be good to see if they understand the differences between n^2 and an n log n algorithms, only because you want to see if they understand the basic concepts of performance in algorithms versus performance in code.
Why not ask applicants to submit examples of projects they've done or code they've written, pick a few that look interesting to you, find portions of the code or projects that look especially interesting, and ask the candidates about it? You'll get to see what kind of work they do in general, and asking them about their code should weed out the few cheeky bastards that submitted something they didn't actually write.
But, I could ace this interview. Hell, I independently developed sorting networks back in about 2002. Present me with a problem and I can probably roll out a pretty good algorithm for solving it, on the spot.
But no startup should ever want to hire me. I'd sink them single-handedly.
So I really don't think that sorting algorithms is the right kind of question for a startup to be asking its candidates.
A good developer will Just Get Things Done. Thats a much more valuable skill then having memorized how to write an insertion sort.
Any developer should be able to build a simple bubble sort with one hand tied behind his back. It doesn't matter that they've never had to do it before because a bubble sort is pretty obvious.
If someone can't throw a simple sort together in a few minutes -- what hope is there that they'll be able to do work worth paying for?