Insertion sort vs Merge sort - memory access

I am a computer science sophomore doing a data structures and algorithms course. My professor said that insertion sort requires random access, while merge sort does not.

According to him, the insertion step in insertion sort requires random access. But can't it be implemented using sequential access in a linked list, going through each element, and as soon as you find that the element of the next node is more than the element you wish to insert, you squeeze that element after the current element (for ascending order list).

He is almost never wrong, but he also doesn't entertain doubts, due to which I'm forced to ask here. Please let me know. Thanks!

The implementation of merge sort that your instructor has in mind accesses memory sequentially, in the sense that merging steps from left to right over the two arrays being merged and the target array as well. Insertion sort has a more complicated memory access pattern.

As you note, if you sort linked lists instead of arrays, insertion sort also conceptually moves from left to right. However, the implementation of linked lists will still do pointer operations that lead to non-sequential memory access.

StackExchange Computer Science Q#70958, answer score: 2