18 ms·
funny you should bring up merge sort: in my first google phone screen, I was asked "why is merge sort good" and I gave "it's asymptotically optimal and stable"
by leif 15y ago
funny you should bring up merge sort: in my first google phone screen, I was asked "why is merge sort good" and I gave "it's asymptotically optimal and stable" and couldn't come up with anything else, the interviewer eventually conceded that I was too young to know that it was also better than other sorting algorithms on tape :)
- andrewf 15y agoCS professors always bring up the tape example, but it's true for any medium where linear access is faster than random, which becomes applicable as you move down from L1 cache -> memory -> local disk -> network. Linked lists, too :)
- leif 15y agoof course, only years later would I understand the proof of why: M/B-way merge sort is optimal in external memory