How to sort a large list of elements where everything is sorted but k elements?

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

StackExchange Computer Science Q#114957, answer score: 2