# 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?

• I think this is a bit vague. I mean really, for sorting a list of 6 elements, take any sensible sorting algorithm that solves the problem. It looks nearly sorted, so maybe the question is asking for a suitable sorting algorithm for such a case. – Juho Apr 13 '15 at 19:46
• @Juho right, that's why I am having problems answering the question. It seems like there are many algorithms that would work just fine, therefore I'm not sure which one would be 'optimal' – Jaken Herman Apr 13 '15 at 19:47
• I think there is a difference in the number of comparisons made by each. Is the number of comparisons made correct? – Jake Apr 13 '15 at 19:51
• The question seems to be about what algorithm would be fastest for this specific example. In such a case, complexity does not matter. But your guess is as good as mine. – babou Apr 13 '15 at 21:32
• Take all the algorithms you know (from class, I assume), execute them (on paper) and count comparisons, swaps, number of executed statements. Which wins? That one. – Raphael Apr 13 '15 at 22:02

An inversion in a permutation $\pi(1),\ldots,\pi(n)$ is a pair of indices $i < j$ such that $\pi(j) < \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)$.