Incorrect number of inversions in array

Question

Could you please help me to find a mistake in my code on C# for counting inversions in array? The count is incorrect. For instance, in array {3, 8, 6, 1} it should be 4, but it's 3. However, it works fine for array {4, 3, 2, 1} and shows 6. Every string from a text file (1111.txt )that program reads, contains 1 array element. Thank you.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace C
{
class Program
{
public static long k1 = 0;
static long Marge_sort(int[] A, int p, int r)
{
int q = p;
if (r <= p) return 0;
q = (p + r) / 2;
C.Program.k1 = Marge_sort(A, p, q);
C.Program.k1 += Marge_sort(A, q + 1, r);
C.Program.k1 += Marge(A, p, q, r);
return C.Program.k1; 
}
static long Marge(int[] A, int p, int q, int r)
{
long k1 = 0;

int n1 = q - p+1 ;
int[] L = new int[n1+1];
int n2 = r - q;
int i;
int[] R = new int[n2+1];
for(i=0;i<n1;i++)
{
L[i] = 0;
L[i] = A[p + i ];
}
L[n1] = int.MaxValue;
for (i = 0; i < n2; i++)
{
R[i] = 0;
R[i] = A[q + i+1];
}
R[n2] = int.MaxValue;
int j = 0; i = 0;
for(int k=p;k<=r;k++)
{
if (L[i] <= R[j])
{
A[k] = L[i];
i++;
}
else
{
A[k] = R[j];
j++;
k1 = q - i+1 ;
}

}
return k1;

}
static void Main(string[] args)
{
long k1 = 0;
int leght = 0, el = 0;
int[] Ch = new int[leght];
StreamReader s = File.OpenText(@"D:\1111.txt");//IntegerArray
string read = null;
while ((read = s.ReadLine()) != null)
{
//Console.WriteLine(read);
leght++;
Array.Resize(ref Ch, leght);
Ch[el] = Convert.ToInt32(read);
el++;
}
s.Close();
k1=Marge_sort(Ch, 0, leght-1 );

Console.WriteLine("\n"+k1.ToString());
Console.ReadLine();

}

}
}

Answer 1

The line close to the end of Marge

k1 = q - i+1 ;

should be

k1 += n1 - i;

Firstly you are keeping a running total of how many elements of L an element of R has to be moved in front of. Therefore the operator should be += not =.

Secondly q measures a position in the original array A. You are counting a number of elements in the small array L, and so you should be subtracting the index from n1, the size of that array (not including the guard value). If A were huge, you would start to see crazy results: when you were merging small sub-arrays with only a few elements, but very close to the top of A, you would see huge values for q, which have nothing to do with the size of L.

When you've made sure your code is working, you should head over to codereview.stackexchange.com. They only help with working code, but they will give you lots of pointers about how to write things in a cleaner and more readable way. Your code is full of small errors like unnecessary namespaces, unused initializations and so on (but I think it is the correct approach to get it working right before worrying about these).

Answer 2

For array {3, 6, 8, 1} the correct answer is 3:

{3, 6, 8, 1} -> {3, 6, 1, 8} -> {3, 1, 6, 8} -> {1, 3, 6, 8}