I'm almost certain this is why I failed my phone interview. It wasn't that I implemented an inefficient sort right away, its that I didn't talk about how/why it was and what I could do about it with more time.
I really don't like the idea of solving contrived puzzles, but I'll never make the mistake of keeping my thought process hidden again.