I actually had read the algorithms of merge and quick sort in the morning. I thought I remembered these basic algos. So I started but in no time it I got struck. I knew how insertion sort works in theory, so I started building up my own algo. When I was finished, I showed him my work. He started reading it line by line and he told me that my algo has O(n^3) complexity while insertion sort has O(n^2) so I should try something else. Then I again started fresh but this time I ended up with an algorithm that is somewhere between bubble and insertion sort. He read my code and he asked me to explain the algorithm. (I had written in my resume that I have teaching experience). So, I explained the algorithm in a manner that is very easy to understand. He then asked me what I have done in my code? I read the code and started explaining him line by line. Then he told me this is closer to bubble sort. Then he told me to leave it.