# What is a partially sorted array?

I come across this definition but it's not so clear for me !

An array is partially sorted if the number of inversions is less or equal a constant times the array length. if array length is N then (number of inversions) <= c*N, with c constant.

For me c should be <= 1 is this what they meant ?

For more context : insertion sort running time is linear for partially sorted arrays.

• Is $c$ fixed or do you get to choose it? I guess the definition wants to be "an array is $c$-partially sorted ... $\leq cN$". – Raphael Sep 22 '15 at 14:32

The definition you quote is rather meaningless. More accurately, a sequence of arrays, one of each length $n$, is partially sorted if for some constant $c$, the number of inversions of the array of length $n$ is at most $cn$. (More succinctly, a sequence of arrays is partially sorted if the number of inversions is $O(n)$.) The running time of insertion sort on such a sequence of arrays is $O(n)$, that is, linear.
It doesn't make much sense to say that a single array is partially sorted, since we can always choose $c$ to make the definition hold. If we want to talk about a single array then we need to fix $c$ in advance. Note that $c$ doesn't have to be at most $1$.
• @morfioce Any collection of arrays of length 4 is partially sorted (with $c=1.5$). Same goes for any collection of arrays of length at most $n$, with $c=(n-1)/2$. – Yuval Filmus Sep 22 '15 at 13:59