2

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!

Improve this question
5
  • Isn't what you are describing as solution a bubble-sort-like implementation?
    – Pieter B
    Feb 28, 2017 at 9:13
  • 2
    Presumably, your professor has a binary search in mind for finding the insertion point (which requires random access, but has O(log N) running time), while you are describing a linear search for the insertion point (which doesn't require random access, but has the higher O(N) running time).
    – Bart van Ingen Schenau
    Feb 28, 2017 at 9:51
  • @BartvanIngenSchenau that makes sense. You could be right
    – James Bond
    Feb 28, 2017 at 10:36
  • @PieterB how do you mean? I am just using a linear search approach to find the right element where insertion of the element must take place.
    – James Bond
    Feb 28, 2017 at 10:38
  • 1
    @PieterB it's actually what wikipedia is describing for insertion sort en.wikipedia.org/wiki/Insertion_sort . There the linear scan is interleaved with the swapping, the while j > 0 and A[j-1] > A[j] loop
    – Caleth
    Feb 28, 2017 at 12:00

2 Answers 2

Reset to default
1

Ok, so I asked this question on the theoretical CS stack exchange website.

Louis has given what I think is the most suitable answer to this question:

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.

That is, when I am inserting a new node at an arbitrary location in the linked list, I am assuming I have random access. Else, I would have to shift all the subsequent nodes ahead in memory before adding the new one.

Improve this answer
0

Wikipedia describes a variant of insertion sort that requires random access to binary search for the insertion point, noting that it is useful in the case where comparisons are much more expensive than swaps. This is labeled "binary insertion sort", but this could well be what your professor is talking about.

It's average and worst case complexity is O(n^2) swaps and O(nlogn) comparisons, which is better than the O(n^2) swaps and comparisons in your method.

If you are operating on a data-structure, such as a heap, with O(logn) insert and O(logn) search, then it becomes overall O(nlogn). This would normally be described as heap-sort or similar.

Improve this answer

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.