competitive finding inversion count

[karmaakabane]

i have implemented merge sort via:

#include<bits/stdc++.h>
using namespace std;
int merge(int *a,int low,int high,int mid)
{
	int i,j,k,temp[high-low+1],count=0,count2=0;
	i=low;
	k=0;
	j=mid+1;
	while(i<=mid&&j<=high)
	{
		if(a[i]<a[j])
		{
			temp[k]=a[i];
			k++;
			i++;
		}
		else
		{
			temp[k]=a[j];
			k++;
			j++;
			count+=mid-i;
		}
	}
	while(i<=mid)
	{
		temp[k]=a[i];
		k++;
		i++;
	}
	while(j<=high)
	{
		temp[k]=a[j];
		k++;
		j++;
	}
	for (int i = low; i <= high; ++i)
	{
		a[i]=temp[i-low];
	}
}
int mergesort(int *a,int low,int high)
{
	int mid=0;
	if(low<high)
	{
		mid=low+(high-low)/2;
		mergesort(a,low,mid);
		mergesort(a,mid+1,high);
		merge(a,low,high,mid);
	}
}
int main()
{
	int n,i;
	cin>>n;
	int a[n];
	for (int i = 0; i < n; ++i)
		cin>>a[i];
	for (int i = 0; i < n; ++i)
		cout<<a[i]<<" ";
}

Now how to find inversion count using merge sort ??

[tpb]

Firstly, please use code tags to retain your indentation:
[code]
your code here
[/code]

Secondly, mergesort should probably return something if you're going to print its return value.

You still get the wrong answer, though, due to the way you are handling mid in merge. A couple of tweaks there and you'll get the right answer.

BTW, this is just a crutch:

#include<bits/stdc++.h> 

If you don't know what header to use, look it up. Learn it.

C++ dosn't have VLAs. So this is illegal.

    cin >> n;
    int a[n];

It should be

    cin >> n;
    int *a = new int[n];   // and remember to delete a; at the end 

Same with temp in merge, although it would be more efficient to allocate a temp array in a mergesort function that calls a recursive mergesort_r "helper" function.

int mergesort(int *a, int size) {
    int *temp = new int[size];
    int count = mergesort_r(a, temp, 0, size - 1);
    delete [] temp;
    return count;
}

[karmaakabane]

@tpd 1 i didnt knew about code tag as its my first forum took care of it,
2 its illegal but still works like a charm so ignore it for now
3 its not necessary it should return anything as the array is passed via pointer so it will just update the same array and i have edited the code and printed the array to show you that it works just fine
4 *most imp i am looking a way to find inversion count and not print the sorted array so look inti it after reading what inversion count is.

[tpb]

I know exactly what "inversion count" is and was able to make your code work with just a couple of simple fixes.

I'm not an idiot so I realize that the array is "passed via pointer" (duh) and will be updated. Who the f cares? That's not the point, is it!?

Obviously it IS NECESSARY THAT IT RETURNS SOMETHING since you are trying to print it's return value (although you've changed the code from the original). And it says it returns an int but it doesn't return anything. I showed you the fix I made for that.

The other fix has to do with how you are handling mid in merge. But if you're too lazy to even fix the VLA thing then I guess I'll be lazy, too. Good night.

[karmaakabane]

I may have misinterpreted what you were saying somewhere along the line.I undid my changes to original merge sort code so you it can be easy for you to tell me where i was going wrong.i am not lazy about handling vla its just that i recently switched to c++ and don't know how to properly handle it that why i asked you to leave for now as i didn't wanted to screw it anymore.if you still want to help in making changes to current code i am all ears and be much appreciated if you could send code so i could understand vla thing implementation and changes much better.