3 ms·
Indeed, this post falls into the category "things that people often rediscover". Using storage optimized data structures and algorithms is very, very old. [ ht
by ynniv 15y ago
Indeed, this post falls into the category "things that people often rediscover". Using storage optimized data structures and algorithms is very, very old.
[ http://en.wikipedia.org/wiki/Merge_sort#Use_with_tape_drives http://en.wikipedia.org/wiki/Merge_sort#Use_with_tape_drives ]
- leif 15y agofunny 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