I think the general approach in an interview would be to ask the person being interviews "can you explain what time function that runs in".. "can you improve it", and see if they work out the "sort" trick by themselves.
That's how it was done to me anyway (although I talked it through before I started writing, and by the time I got actually writing anything down I'd worked out the trick).
That's how it was done to me anyway (although I talked it through before I started writing, and by the time I got actually writing anything down I'd worked out the trick).