What sorting algorithm should be used for this array? I am given an array {1, 2, 3, 5, 4, 6} and I am asked 


  What sorting algorithm might you want to use to sort the given list, and why?


Initially I think using Bubble sort would be the best option due to it's best case linear ($O(n)$) complexity and due to the fact that you'd only need to use 1 swap. However, the more I look at the problem I am starting to think that Insertion Sort may also be efficient in this situation.

Insertion sort and Bubble sort both have the same best, average, and worst case time complexities as well as the same space complexities. Are neither one of these algorithms the proper one to be used on this array? If not, why not?
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)$.