0

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 
  • *There are no errors* -- Why do you say there are no errors, but the output isn't correct? Your program has one or more bugs -- have you used the debugger? – PaulMcKenzie Nov 12 '21 at 18:10
  • Seems that you forgot to adjust the start of the first subarray in `merge_two_arrays`. It should be something like `merge_two_arrays(p1 + si,mid1-si,p1+mid1+1,ei-mid1-1,p2);` – Aivean Nov 12 '21 at 18:13
  • 2
    *Any help on where exactly I'm going wrong* -- [What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). – PaulMcKenzie Nov 12 '21 at 18:14
  • I did try using the debugger @PaulMcKenzie, but the recursion part got too confusing for me to understand, I will ofcourse try to debug it and understand it again, but thought asking would provide a fresh perspective. – theory_in_progress Nov 12 '21 at 18:18
  • Oh yeah! I should've added the `p1+si` while calling the function, thanks @Aivean! – theory_in_progress Nov 12 '21 at 18:20
  • Regarding [There are **no errors**.](https://godbolt.org/z/ETWrYzTzv) Be very careful with bits/stdc++.h and prefer to [not use it directly at all](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). Adding `using namespace std;` [can make things get really weird](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). – user4581301 Nov 12 '21 at 18:24
  • 3
    @theory_in_progress *According to me, the below code should work.* -- The issue is that you wrote the code with a plan in mind. The code took a different path than what you had planned. All code that you write, you *must* be able to understand every line, and debug the code if there are issues. You cannot simply write code, say "it looks right", see that it doesn't work correctly, and not understand the code that *you* wrote to the point it confuses you. If that's the case, it's time to go back and write on paper *exactly* what you are expecting the program to do. – PaulMcKenzie Nov 12 '21 at 18:28
  • 1
    Recommendation: Build the input into the program while debugging it allows you to run the program over and over with no variation quickly. – user4581301 Nov 12 '21 at 18:29
  • 1
    Where Paul is headed is if there were incorrect assumptions in the development of the program, you'll be parroting the same incorrect assumptions as you debug. The debugger doesn't care what you think the code should do, it shows you what the code does. Hard on the ego sometimes, but an invaluable second opinion. Were I to take on this question, I'd run it in a debugger and start stepping through with a very small input set that I know will fail while keeping an eye out for where the program doesn't meet my expectations. – user4581301 Nov 12 '21 at 18:33
  • Sorry! yep it was wrong of me to assume everything I did was correct and that according to me the program should run correctly, I will give the debugger another try, thanks for the inputs! – theory_in_progress Nov 12 '21 at 18:39
  • @theory_in_progress you might find this article very helpful: https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ – SergeyA Nov 12 '21 at 19:26

0 Answers0