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)$.

  • $\begingroup$ 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). $\endgroup$ Aug 19, 2018 at 15:42
  • $\begingroup$ 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? $\endgroup$ Aug 19, 2018 at 15:52
  • $\begingroup$ 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)$! $\endgroup$
    – user46107
    Feb 22, 2020 at 19:48

1 Answer 1


Best case performance is attained when only one element is not in place. Assume the following list


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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