[Solved]: It is possible to implement insertion sort for sorting linked list ?

Problem Detail: 

it is possible to implement insertion sort for sorting linked lists ? will it have the same O(n^2) efficiency as the array version ?

Asked By : ghostloops

Answered By : David Richerby

This question is fully answered by the Wikipedia page on insertion sort. In summary, yes, you can implement insertion sort on a linked list with the same efficiency as for an array because insertion sort only makes sequential accesses to the data being sorted. Every time it accesses the data, it's looking at "this element", "the next/previous element" or "that element I was looking at a few moments ago and whose index/position in the list I already stored."

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42637

 Ask a Question

 Download Related Notes/Documents