Code:
// Merge sort
#include <iostream>
#include <algorithm>
using namespace std;
void Merge(int *A, int *B1, int one, int *B2, int two){
int *combi = new int[one+two];
int c = 0, d = 0, x=0;
while(c < one && d < two){
cout<<"B1[C] "<<B1[c]<<" B2[d] "<<B2[d]<<endl;
if(B1[c] < B2[d]){
combi[x] = B1[c];
cout<<"combi[x] = "<<combi[x]<<endl;
c++;
}
else{
combi[x] = B2[d];
cout<<"combi[x] = "<<combi[x]<<endl;
d++;
}
x++;
}
while(c < one){
combi[x] = B1[c];
x++;
c++;
}
while(d < two){
combi[x] = B2[d];
x++;
d++;
}
cout<<"combi is ";
for(int f = 0; f<one+two; f++) cout<<combi[f]<<' ';
cout<<endl<<endl;
}
void MergeSort(int *A, int n){
if (n > 1){
int *B1 = new int[n/2];
int *B2 = new int[n - n/2];
for(int x = 0; x < n/2; x++){B1[x] = A[x];}
for(int x = 0; x < n - n/2; x++){B2[x] = A[x + n/2];}
cout<<endl<<"B1 is ";
for(int x = 0; x < n/2; x++)cout<<B1[x]<<' ';
cout<<endl<<"B2 is ";
for(int x = 0; x < n - n/2; x++)cout<<B2[x]<<' ';
cout<<endl;
MergeSort(B1, n/2);
MergeSort(B2, n - n/2);
Merge(A, B1, n/2, B2, n - n/2);
}
}
int main() {
int A[ ] = {4,2,6,1};
MergeSort(A, 4);
cout<<endl<<endl<<"final A: "<<endl;
for (int i=0; i < 4; i++) cout << A[i] << " ";
return 0;
}
Output:
B1 is 4 2
B2 is 6 1
B1 is 4
B2 is 2
B1[C] 4 B2[d] 2
combi[x] = 2
combi is 2 4
B1 is 6
B2 is 1
B1[C] 6 B2[d] 1
combi[x] = 1
combi is 1 6
B1[C] 4 B2[d] 6
combi[x] = 4
B1[C] 2 B2[d] 6
combi[x] = 2
combi is 4 2 6 1
final A:
4 2 6 1
As you can see, the code runs smoothly at the start, sorting 4 2 and 6 1. However, it seems this sort is only temporary as when B1 and B2 try to combine afterwards, they end up becoming the same numbers as before. Does this have something to do with my usage of pointers?
It seems like the code messes up after the "combi is 1 6" line in the output. Does anyone have any idea what is going on and how to fix this?
Your code has a problem with Merge. At the entrance to the function you expect that the array after merging will be written in argument A, but in reality it is written in the local variable combi, which you do not use anywhere, and accordingly it does not affect the result
To solve this problem simply in the Merge function replace each call of the variable combi in call A.
The result should be something like this. NOTE: I also added freeing memory, but in general I haven't made code cleaner
#include <iostream>
#include <algorithm>
using namespace std;
void Merge(int *A, int *B1, int one, int *B2, int two){
int c = 0, d = 0, x=0;
while(c < one && d < two){
cout<<"B1[C] "<<B1[c]<<" B2[d] "<<B2[d]<<endl;
if(B1[c] < B2[d]){
A[x] = B1[c];
cout<<"combi[x] = "<<A[x]<<endl;
c++;
}
else{
A[x] = B2[d];
cout<<"combi[x] = "<<A[x]<<endl;
d++;
}
x++;
}
while(c < one){
A[x] = B1[c];
x++;
c++;
}
while(d < two){
A[x] = B2[d];
x++;
d++;
}
cout<<"combi is ";
for(int f = 0; f<one+two; f++) cout<<A[f]<<' ';
cout<<endl<<endl;
}
void MergeSort(int *A, int n){
if (n > 1){
int *B1 = new int[n/2];
int *B2 = new int[n - n/2];
for(int x = 0; x < n/2; x++){B1[x] = A[x];}
for(int x = 0; x < n - n/2; x++){B2[x] = A[x + n/2];}
cout<<endl<<"B1 is ";
for(int x = 0; x < n/2; x++)cout<<B1[x]<<' ';
cout<<endl<<"B2 is ";
for(int x = 0; x < n - n/2; x++)cout<<B2[x]<<' ';
cout<<endl;
MergeSort(B1, n/2);
MergeSort(B2, n - n/2);
Merge(A, B1, n/2, B2, n - n/2);
delete[] B1;
delete[] B2;
}
}
int main() {
int A[ ] = {4,2,6,1};
MergeSort(A, 4);
cout<<endl<<endl<<"final A: "<<endl;
for (int i=0; i < 4; i++) cout << A[i] << " ";
return 0;
}
P.S. If it is available in your case, you should switch your code from raw pointers to std::vector, from own Merge function to std::merge, from copying arrays elements by elements to std::copy