Sort an array with a constant number of unsorted elements
Denote the array by $A_1,\ldots,A_n$. If $A_i &gt; A_{i+1}$ then at least one of the two elements is out of place. We scan the array, and each time we find such a pair, we remove both elements. In $O(n)$ time, we obtain a sorted subarray $B$ together with $O(1)$ many unsorted elements, forming a set $C$. We sort $C$ in $O(1)$ and merge it with $B$ in $O(n)$.