I'm learning merge sort algorithm, using recursion. According to me, the below code should work. There are no errors, but the final sorted array is not actually sorted. Any help on where exactly I'm going wrong is appreciated! Is my concept correct?
#include <bits/stdc++.h>
using namespace std;
void merge_two_arrays(int *a1, int sizea1, int *a2, int sizea2, int *a3) {
int i=0, j=0, k=0;
while(i<sizea1 && j<sizea2) {
if(a1[i]<=a2[j]) {
a3[k++] = a1[i++];
}
else {
a3[k++] = a2[j++];
}
}
while (i < sizea1) {
a3[k++] = a1[i++];
}
while (j < sizea2) {
a3[k++] = a2[j++];
}
}
void merge_sort(int *p1, int si, int ei, int *p2) {
if(si>=ei) {
return;
}
int mid1=(si+ei)/2;
merge_sort(p1,si,mid1, p2);
merge_sort(p1,mid1+1,ei, p2);
merge_two_arrays(p1,mid1-si,p1+mid1+1,ei-mid1-1,p2);
}
int main() {
int n;
cin>>n;
int *p = new int[n];
for(int i=0;i<n;i++) {
cin>>p[i];
}
int *p1 = new int[n];
merge_sort(p, 0, n-1, p1);
for(int i=0;i<n;i++) {
cout<<p1[i]<<" ";
}
delete []p;
delete []p1;
return 0;
}
My Input -
7
38 27 43 3 9 82 10
Output -
9 38 27 43 82 0 0