views:

331

answers:

1
void MergeSort(int A[], int n, int B[], int C[])
{ 
    if(n > 1)
    {
       Copy(A,0,floor(n/2),B,0,floor(n/2));
       Copy(A,floor(n/2),n-1,C,0,floor(n/2)-1);
       MergeSort(B,floor(n/2),B,C);
       MergeSort(C,floor(n/2),B,C);
       Merge(A,B,0,floor(n/2),C,0,floor(n/2)-1);
    }
};

void Copy(int A[], int startIndexA, int endIndexA, int B[], int startIndexB, int endIndexB)
{
    while(startIndexA < endIndexA && startIndexB < endIndexB)
    {
        B[startIndexB]=A[startIndexA];
        startIndexA++;
        startIndexB++;
    }
 };

 void Merge(int A[], int B[],int leftp, int rightp, int C[], int leftq, int rightq) 
//Here each sub array (B and C) have both left and right indices variables (B is an array with p elements and C is an element with q elements)
{ 
    int i=0;
    int j=0;
    int k=0;

    while(i < rightp && j < rightq)
    {
        if(B[i] <=C[j])
        {
            A[k]=B[i];
            i++;
        }
       else
       {
            A[k]=C[j];
            j++;
            inversions+=(rightp-leftp); //when placing an element from the right array, the number of inversions is the number of elements still in the left sub array.
        }
        k++;
  }
  if(i=rightp)
      Copy(A,k,rightp+rightq,C,j,rightq);
  else
      Copy(A,k,rightp+rightq,B,i,rightp);
}

I am specifically confused on the effect of the second 'B' and 'C' arguments in the MergeSort calls. I need them in there so I have access to them for Copy and and Merge, but

A: 

I apologize for the ambiguity here. Here is the output:

Input (A)=  4   2   53  8   1   19  21   6 
 19 
 19 
 21  
 19 
 21 
 19 
 21 
 6 
 inversions=9

Obviously that is not the correct result for the array, and by my count, the inversions should equal 16. Any help or comments would be greatly appreciated. (even criticism too! ;)

Brown