Calculate number of (binary) inversions

Hello!

I'm looking for an algorithm that counts the number of binary
inversions in theta(n) or "normal" inversions in nlog(n).

A sample for binary inversion: (1,0,1,1,0) has 4 inversions: (0,1),
(0,4), (2,4), (3,4).
A sample for normal inversion: (3,1,2,5,4)has 3 inversions: (0,1) (
3>1), (0,2) ( 3>2) (3,4) ( 5>4)

I am writing this question into the theory-group, because I develop the
programm in Perfect Developer (http://www.eschertech.com/).

Thank you,

.

Relevant Pages

  • Re: How to prove that a random sort algorithm converges?
    ... The number of transpositions needed is the number of inversions, ... upperbound" for the algorithm is a good point. ... runs forever without any determination that the array has been ... (because the actual swaps will reach the theoretical maximum ...
    (sci.math)
  • Re: How to prove that a random sort algorithm converges?
    ... The number of transpositions needed is the number of inversions, ... why I pushed him toward reasoning about inversions. ... upperbound" for the algorithm is a good point. ...
    (sci.math)
  • Re: How to prove that a random sort algorithm converges?
    ... I randomly select a pair of two numbers at adjacient poisitions, ... and I swap their position if the value at position i is ... how do I prove that this algorithm converges? ... I'd try proof by induction on the number of inversions. ...
    (sci.math)