Assuming the list is very large, and $k$ is very small, what's the fastest algorithm to sort this list?
Here is an $O(k \log k + n)$ Algorithm. Assuming we are dealing with an ascending order. We assume $A$ is a linked list, an hence removing elements can be done in constant time. Given an array instead, we can preprocess it in linear time building a linked-list out of it.
Let A be a given list of n elements. Let B be an empty array. For x in A do - Let y be the element following x. - As long as y < x then - - Add x to B. - - Add y to B. - - Remove x from A. - - Remove y from A. - - If x was the first element, - - - then break from the inner loop. - - Set x to the previous element of x. - - Set y to the following element of y. Sort B with any efficient sorting algorithm. Unify A and B in the array C efficiently. Return the array C.
If an element $x$ is greater than the following element $y$, then at least on of them must be one of the $k$ elements, because else they must be sorted. Hence, we do not remove more than $2k$ elements from $A$. Since with each visit of the inner-loop except for the last one, we remove two elements from the array, and since we do not remove in total more than $2k$ elements, the total number of visits of the inner loop is at most $2k+n$. The size of $B$ is at most $2k$, since it only has the elements removed from $A$. Using quick-sort, we can sort $B$ in running time $O(k \log k)$ (note that $B$ is an array and not a list). Unifying two sorted arrays/lists in a new sorted list can be achieved in linear time using sliding-window. The total running time is $O(n + 2k + k \log k + n + k) = O(k \log k + n)$.