# 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, 2015 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'
– Jud
Apr 13, 2015 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, 2015 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. Apr 13, 2015 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, 2015 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)$.