3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Your implementation of linked lists also needs to be able to access memory non-sequentially for the pointer operations that splice in the new value. $\endgroup$ – Louis Feb 28 '17 at 11:21
  • $\begingroup$ @Louis I think you are spot on! I did not think of that. That is most definitely the correct explanation. If you had written that as an answer I would choose it as the right one : ) $\endgroup$ – James Bond Feb 28 '17 at 17:49
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

You are over-thinking things here. By 'random access', you professor merely means that insertion requires access to an arbitrary location in the already-sorted sublist, regardless of how that location is found. By contrast, with merge sort, each element move during a merge pass requires only that some element be taken off of the front of one list and moved to the end of another list; no other list locations need be considered.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.