# Thread: Divide and Conquer Merge_sort

1. ## Divide and Conquer Merge_sort

This code is supposed to sort an array using the divide-and-conquer method. But I think I mixed up the index.
Code:
```#include <iostream>

using namespace std;

void Merge(float *A , int p , int q , int r)
{
int n1 = q - p + 1;
int n2 = r - q;
float *L = new float [n1];
float *R = new float [n2];
int i , j;
for ( i = 0 ; i < n1 ; i++)
L[i] = A[p + i -1];

for ( j = 0 ; j < n2 ; j++)
R[j] = A[q + j];

i = 1;
j = 1;

for ( int k = p; k <= r ; k++)
{
if ( L[i] <= R[j])
{
A[k] = L[i];
++i;
}
else if (A[k] == R[j])
{
++j;
}
}

delete [] L;
delete [] R;
}

void Merge_Sort(float *A, int p, int r)
{
if ( p < r )
{
int q = (p+r)/2;
Merge_Sort(A,p,q);
Merge_Sort(A,q+1,r);
Merge(A,p,q,r);
}
}

int main()
{
int n = 8;
float A[] = {5,2,4,7,1,3,2,6};
for ( int i = 0 ; i < 8 ; i++)
std::cout << A[i] << std::endl;
Merge_Sort(A,1,7);
cout << endl;
for ( int i = 0 ; i < 8 ; i++)
std::cout << A[i] << std::endl;
return 0;
}```
The array to be sorted is:
Code:
`A={5,2,4,7,1,3,2,6}`
the sorted array should be:
Code:
`1 2 2 3 4 5 6 7`
However, what i get is:
Code:
`5 0 0 0 0 0 0 6`
This is just replacing the point in the middle of the original array A with 0. I don't understand why it's doing this. Any input is well appreciated.

2. All your array indices appear to be one off, but not really in a consistent manner. You start things at 1 instead of 0, you split A[q] with the first group, but your merge uses A[q] as the first element in the second group. And so on.

3. Originally Posted by tabstop
All your array indices appear to be one off, but not really in a consistent manner. You start things at 1 instead of 0, you split A[q] with the first group, but your merge uses A[q] as the first element in the second group. And so on.
I've been working on this to fix the indexing.
Code:
```#include <iostream>

using namespace std;

void Merge(float *A , int p , int q , int r)
{
int n1 = q - p + 1;
int n2 = r - q;
float *L = new float [n1];
float *R = new float [n2];
int i , j;
for ( i = 0 ; i < n1 ; i++)
{
L[i] = A[p + i];
}

for ( j = 0 ; j < n2 ; j++)
{
R[j] = A[q+1+j];
}

i = n1-1;
j = n1-1;

for ( int k = r; k >= p ; k--)
{
if ( L[i] >= R[j] )
{
A[k] = L[i];
L[i] = 0;

if( (i-1) >= 0)--i;
}
else
{
A[k] = R[j];
R[j] = 0;
if( (j-1) >= 0) --j;
}
}
delete [] L;
delete [] R;

}

void Merge_Sort(float *A, int p, int r)
{
if ( p < r )
{
int q = (p+r)/2;
//cout << "p=" << p << " q=" << q <<  " r=" << r << endl;
Merge_Sort(A,p,q);
Merge_Sort(A,q+1,r);
Merge(A,p,q,r);
}
}

int main()
{

float A[] = {30,20,25,52,32,26,78,79,2,3};
// int n = sizeof(A)/sizeof(float);
int n=10;
cout << n << endl;

for ( int i = 0 ; i < n ; i++)
std::cout << A[i] << "   ";
cout << endl;

Merge_Sort(A,0,7);

cout << endl;

for ( int i = 0 ; i < n ; i++)
std::cout << A[i] << " ";
cout << endl;
return 0;
}```
The strange thing is, this will only works if I sort 8 elements in the array. If I choose to sort more element, it won't work and some value of A is changed to 0.
What's wrong with this?

4. Code:
```i = n1-1;
j = n1-1;```
Oops!

5. Originally Posted by tabstop
Code:
```i = n1-1;
j = n1-1;```
Oops!
Thank you. That was such a stupid mistake. I thought of using n2,, but still put down n1.