# 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

## 1 Answer

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$.

• The sequence should be unbounded in array size. – Yuval Filmus Sep 22 '15 at 13:02
• To make sure that I get your point let say we have the following sequence of arrays : [10, 20, 5, 25], [100, 200, 50, 250], [1000, 500, 2000, 3000] here n = 4, and c is 1/2 so the number of inversion <= cn = 2; thanks for the detailed answer. – morfioce Sep 22 '15 at 13:20
• @morfioce I repeat my comment: the sequence of arrays should be unbounded in length. Otherwise you can "cheat". – Yuval Filmus Sep 22 '15 at 13:22
• Can you explain it a bit with an illustrative example ? thanks :) – morfioce Sep 22 '15 at 13:46
• @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