マージソートを使用して配列の反転をカウントするプログラムを実装しました。プログラムはマージソートと同じですが、反転カウントがわずかに異なります。
public class HMergeSortVer1 {
public int inversions;
public void msort(int [] A,int p, int r){
if(p<r){
int q=(int) Math.floor((r+p)/2);
// System.out.println("q--"+q);
msort(A, p, q);
msort(A, q+1, r);
merge(A,p,q,r);
}
}
private void merge(int [] A,int p,int q,int r){
//System.out.println("In the merge");
int n1=q-p+1; // number of elements in left array
int n2=(r-q);
int[] L=new int[n1+1];
int[] R=new int[n2+1];
for(int i=0;i<n1;i++){
L[i]=A[p+i];
}
for(int j=0;j<n2;j++){
R[j]=A[q+j+1];
}
L[n1]=Integer.MAX_VALUE;
R[n2]=Integer.MAX_VALUE;
int i=0;
int j=0;
for(int k=p;k<(r+1);k++){
if(L[i]<= R[j]){
A[k]=L[i];
i=i+1;
}
else {
A[k]=R[j];
j=j+1;
int numOFElements=n1-i;
inversions=inversions+numOFElements; // this counts inversion
}
}
}
}
一部のケースでは機能しますが、他のケースでは間違った出力が得られます。何か不足している場合はお知らせください。