The interview started at the job fair in our university. The interviewer gave me a short face-to-face interview after I sent him my resume. He asked me several technical questions, such as what a virtual function is and how to see the process ID in Linux.

Two days later, an HR representative contacted me and invited me to an on-site interview. There were three interviewers, and they all asked for details about my project experiences. I didn't prepare well and couldn't remember some details of the algorithms I used in my projects.

Write a sorting algorithm and tell its complexity.