What sorting algorithm should be used for this array?
An inversion in a permutation $\pi(1),\ldots,\pi(n)$ is a pair of indices $i &lt; j$ such that $\pi(j) &lt; \pi(i)$. Denote the number of inversions by $I(\pi)$. In your example, $I(123546) = 1$. It is well-known that insertion sort runs in time $O(I + n)$ on a permutation of length $n$ having $I$ inversions. Due to this guarantee, insertion sort is asymptotically optimal when the number of inversions is small, $I = O(n)$.