Li Chun’s Count the number of inversions in a sequence

[Original post has malformed and or illegal xhtml constructs – mainly due to the unescaped ‘<‘ within the C++ code:]

An inversions in a sequence A1,A2,…,An of n different integers is defined as a pair of integers (Ai, Aj) satisfying Ai > Aj and i.

The idea is based on merge sort. When merge 2 sequences, A1, A2, …, Am and Am+1, Am+2, …, An, for each Ai>Aj (1<=i<=m and m+1<=j<=n), the counter of inversions add 1 to total value.

Begin Code:

int findInversion(vector* seq, int begin, int end, vector* newSeq) {
if(begin == end) {
(*newSeq)[0] = (*seq)[begin];
return 0;
int result = 0;
int middle = (begin+end)/2;
vector* left = new vector(middle - begin + 1);
vector* right= new vector(end - middle);
result = findInversion(seq,begin,middle,left) + findInversion(seq,middle+1,end,right);
//merge sequence left an sequence right
int iterLeft=0;
int iterRight=0;
int index=0;
if(iterRightsize() && (*left)[iterLeft]>(*right)[iterRight]){
(*newSeq)[index++] = (*right)[iterRight++];
(*newSeq)[index++] = (*left)[iterLeft++];
while(iterRight <>size() ){
(*newSeq)[index++] = (*right)[iterRight++];
//release spaces and return
delete left,right;
return result;

End Code


Comments are closed.

%d bloggers like this: