Let n > 1 be an integer. Let A be an array, indexed from 1 to n, of n values A(i) coming from the finite set {0,1}. (More generally, the values can come from any totally ordered set, but I only need a two element set for now.)

Let us count the number of inversions in A, that is the number of pairs (i,j) with i < j and A(i) > A(j). Using [ ] for Iverson notation, this is

I = sum{ 1 <= i <= j <= n } [A(i) > A(j)]

I call the quantity I/(n^2) the *inversion density*
of A. As an exercise you can show the inversion density
falls in the closed interval [0, 1/4] .

**Question**: Is this (inversion density) or a closely related concept
present in the literature? If so, please tell me where.

I am still wading through the sorting literature, where number of inversions in an array are considered, but I have yet to see anything regarding a density. I have not yet found a successful online search; if a good search term is proffered I will try it as a substitute for a good reference.

Motivation: I did some research on Combsort and was looking for worst case complexity results. After finding some bad (good) cases, I saw that the same ideas had been more fully developed in the two papers listed below. In particular Poonen has a proposition which can be phrased in terms of inversion density as: there is an absolute constant c so that, for any length n 0-1 array A and for any integer j with 1 < j <= n, there is a contiguous length j subarray B (so B(k) = A(l+k-1) for some l and 1 <= k <= j ) such that the inversion density of B is at least c times the inversion density of A .

Poonen shows c >= 1/256. I can tighten his argument to show c >= 1/32, and suspect c = 1/2 . I also suspect the proposition holds for arrays with values from any totally ordered set.

References (Please add to this!):

Mark Allen Weiss and Robert Sedgewick, "Tight Lower Bounds for Shellsort", Journal of Algorithms Volume 11, Issue 2, June 1990, Pages 242-251

B. Poonen, “The worst case in Shellsort and related algorithms,” J. of Algorithms 15, 1993, 101-124.

Gerhard "Ask Me About System Design" Paseman, 2010.07.10