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

• If the array is initially $[M,\ldots,M+k-1,1,2,3,4,\ldots]$ where $M$ is a large number, then your algorithm will have $B=[M+k-1,1]$. Sorting $B$ and unify it with $A$ is not enough to sort the whole array. – xskxzr Sep 21 '19 at 4:30
• You have to be more careful. After you removed two consecutive elements x and y, you must then recheck the element before x. In xskxzr's example, you would remove (M+k-1) and 1, then (M+k-2, 2) and so on. – gnasher729 Sep 21 '19 at 13:47
• @gnasher729, you are right, I will update the solution. However, the running time stays the same with a simple counting argument. Thanks for the note :) – narek Bojikian Sep 21 '19 at 23:03

If you start with a sorted array, and then k array elements are modified, the best would be to keep track of the array indices of the modified elements as they are modified, extract them into a separate array and sort them, then merge both arrays.