# How to implement insertion sort on linked list with best case performance O(n)?

I have an almost sorted linked list containing N distinct elements with only 1 element not in it's place. Every implementation I have seen start insertion from the beginning (unlike insertion sort on arrays) therefore the complexity will be $O(N^2)$.

• Simple: find the element not in its place. This involves a linear scan of the list. Splice the node out of the list. Then, find the element's proper place in the list by performing another linear scan. Finally, insert the node at its proper place. Time complexity: O(N). – Mike Borkland Aug 19 '18 at 15:42
• Thank you. This will work. Aside from situation that I have just one element wrong, is it possible to generally implement insertion sort on linked list with O(n) performance? – Philip Moreira Aug 19 '18 at 15:52
• You need to insert one element for every inversion between neighbors in the input list; if there are $k$ inversions taking at most $n$ each, you get $O(kn)$ performance. If $k$ is a fixed constant, you get $O(n)$. Interestingly, I think if the list is completely reversed, each insertion is at the beginning of the list and takes constant time, so is also $O(n)$! – Daniel M Gessel Feb 22 '20 at 19:48

You can easily show that it takes you $O(n)$ to sort via insertion sort: The inner while loop will run $n$ times when the outer loop reaches node 0. Otherwise, it will never be executed.