Merge sort implementation giving incorrect output

[Mon92]

I've implemented the merge sort algorithm and used the 'merge' part for counting the number of split-inversions in an array as part of an assignment for an online course. How ever, the out put array is not a sorted version of the input array and as a result the number of split inversions obtained is wrong. I think that there is some thing wrong in the way I am indexing arrays.

P.s: I've used ' cout ' to print the values of indexes to see exactly what values are being passed in during the recursions.

[Code]



#include <iostream>
using namespace std;


int length=0,mid=0,inv=0;

void mergesort(int arr[], int first, int last)
{
cout << "first: " << first << " " << "last: " << last;
cout << endl;
void merge_and_countinv(int arr[], int first, int mid, int last);

length = (last - first) + 1;
if(length == 1)
return;
else
{
mid = (last+first)/2;
mergesort(arr, first, mid);
mergesort(arr, mid+1, last);
merge_and_countinv(arr, first,mid,last);
}
}


void merge_and_countinv(int arr[], int first, int mid, int last)
{

int L1 = (mid - first) + 1; // L1 is length for sub-array A
int L2 = last - mid; // L2 is length for sub-array B
int len = L1 + L2;


int A[10], B[10],C[10];

cout << "first, mid, mid+1, last: " << first << " " << mid << " | " << mid+1 << " " << last << endl << endl;

cout << "loop for copying into A" << endl;
for(int i=0; i < L1;i++)
{ // First half of input array into A
A[i] = arr[first + i];
cout << "copying first half: " << A[i] << endl << endl;
}

cout << "loop for copying into B" << endl;
for(int i=0; i < L2; i++)
{ // Second half into B
B[i] = arr[(mid+1)+i];
cout << "copying second half: " << B[i] << endl << endl;
}

int i=0, j=0,temp=0,k=0;

cout << "indexes i and j: " << i << " " << j << endl << endl;


while((i < L1) && (j < L2))
{
if(A[i] > B[j])
{
C[k] = B[j];
j++;
k++;
temp=i;
while(temp < mid+1) // count number of elements left in A which is equivalent of
{ // counting number of split inversions.
inv++;
temp++;
}
}
else if(B[j] > A[i])
{
C[k] = A[i];
i++;
k++;
}
}
if(i==L1)
{
while(j < L2)
{
C[k] = B[j];
j++;
k++;
}
}
else if(j==L2)
{
while(i < L1)
{
C[k] = A[i];
i++;
k++;
}
}

cout << "Copying from temp...";
for(int i=first;i<len;i++)
arr[i] = C[i-first];


cout << endl << endl;

cout << "Sorted array: " << endl << endl;
for(int i=0;i<len;i++)
cout << arr[i];

cout << endl << endl;
}


int main()
{
int arr[] = {9,8,7,6};
mergesort(arr,0,3);
for(int i=0;i<=3;i++)
cout << arr[i] << endl;
cout << endl;
cout << inv;
int x;
cin >> x;
return 0;
}



[Code]

[MiiNiPaa]

Please, do not double post. It clutters forums and spreads attempts to help you. Another thread: http://www.cplusplus.com/forum/beginner/145921/

[Mon92]

Oh I am so sorry. After posting I felt that my post was inappropriate for the Beginner forum hence I' decided to post again on the General forum. I am new to using this web-site's forum. Again, apologies for double posting. I have deleted the post from the Beginner's forum.

[MiiNiPaa]

First of all you have a serious problem with global variables.

Global variable mid will be rewritten by first recursive call of mergesort and second call will take invalid midpoint. This is the cause of your 6 duplication.
You can leave inv global (as it is debug counter which does not participate in logic) but other variables should be local.

I do not have time to delve into merging code right now, but I will check it later.

[Mon92]

Thank you so much MiiNiPaa for pointing me to the problem with the global variables. After declaring them local in the merge-sort routine I got better results, specifically an output array without the duplicate 6 like you mentioned.

After a little more inspection I found that I was not using correct values for the index in the loop used to copy values from the 'temp' array into the input array. After using correct values, the program runs as expected and yields a sorted array.

Now I just have to fix the part of the program used to count the number of split-inversions.


I was very frustrated since quite a few days as I just couldn't find the problem. Thank you once again for your time and pointing to the incorrect use of the global variables! Much appreciated!

P.s: Pardon my naivety but, I did not exactly understand as to how the global variable mid would get re-written by the first recursive call. I mean, it is defined out side the function body of the mergesort routine right. I thought that globally defining and initializing it with zero would enable me to use it as the 'inv' global variable. Does it get re-written because it's address is accessible always any where in the program?

[MiiNiPaa]

mid = (last+first)/2;
mergesort(arr, first, mid);
mergesort(arr, mid+1, last);

if last is 10 and first is 0, mid would be set to 5 and you will expect ypur functions to be called as:

mergesort(arr, 0, 5);
mergesort(arr, 6, 10);

But first recursive call to mergesort will execute same code snippet and set mid to 2. So, assuming no changes to mid would be done in deeper calls actually your second call is mergesort(arr, 2, 10);. And that call modifies mid too so your call to merge functions changes too. In the end you will try to merge two unsorted arrays which will lead to serious problems.