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)$.
3
-
$\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$Mike Borkland– Mike Borkland2018-08-19 15:42:47 +00:00Commented 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$Philip Moreira– Philip Moreira2018-08-19 15:52:59 +00:00Commented 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– user461072020-02-22 19:48:10 +00:00Commented Feb 22, 2020 at 19:48
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Best case performance is attained when only one element is not in place. Assume the following list
1->2->3->4->0
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.
