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

| cite | improve this answer | |
  • 1
    $\begingroup$ 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. $\endgroup$ – xskxzr Sep 21 '19 at 4:30
  • 1
    $\begingroup$ 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. $\endgroup$ – gnasher729 Sep 21 '19 at 13:47
  • $\begingroup$ @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 :) $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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