Hm, I don't think that I can come up with any other sort algorithm on the fly at the moment (at the moment being 00:15 AM at my place). To be truthful, I probably couldn't come up with any other sort algorithm in 9:00 AM either.
The last time that I had to that was in class, and I'm pretty sure that what I did there is topped by the BCL, STL, etc algorithms. Beside, we all know that mergesort is broken. Are those the criteria that people are hiring on?
I can find a good answer in google in about 5 seconds, better yet, I can take my anti-NIH pill and use Array.Sort() (or one of its contemporaries). Is this really what people are asking in interviews? Next they will ask how to copy a file *.
If it not crucial, I don't bother to keep it in my head. There isn't any point, I have limited time and limited ability to digest things, I have better things to do with my time them memorizing things that can be searched. Hell, one of the reasons that I have a blog is that I can refer to it in the future and find the solution to issues that I already solved. Hell, I wrote dozens of SQL Functions, and I still don't remember their syntax.
Why bother asking such questions when 99% of the time the developer is not going to start developing data structures?
My current favoraite question is to solve the Recommend a Product based on the Recent Order riddle. I solved that one (for fun, actually, not for work) in 13 lines of SQL. I like it because it is relevant to what most people will do (although I aim to keep away from the database, I keep getting pulled there :-) ), and it is not something that can be trivially solved by memorizing.
I am actually not interested in the correct answer, that one is too hard to solve on the spot in an interview, but more at how they approach the issue. I got a few good answers on the fly, just talking through the connections between the tables, which was exactly what I wanted to hear.
One of the best interviews that I had was with a developer that answered wrong to most of my questions, but I could see that he thought, and that is so much more important than a head full of data structures and language syntax is.
Oh, and if anyone who is reading this is going to be interviewed by me, don't chear about the solution to the above riddle. The nextx one in the ladder is called Multi Threading Madness :-)
* I am not a good example for this case, it takes me 12,259 lines of code to read a file :-)