Why does Insertion sort take linear time in this case?
Count the number of times each of the 5 new element is moved in the array:
The areay is of length $n$, and thus each of the 5 elements move at most $n$ times. The place of all other elements is correct, and thus there is at most $5n$ swaps required to &quot;correct&quot; the array, hence $O(n)$ swaps.