CODEWITHSUNDEEP
c++mergesort
novice programmer
novice programmer

Reputation: 103

Trying to understand merge sort program

I am trying hard to understand merge sort program.In order to understand I wrote this program but fails to understand the output. It would be very helpful if someone explain the output. I have understood only till mid=0.

 #include <iostream>

 using namespace std;

 void check(int c, int d) {
     cout << "C=" << c << " D=" << d << endl;

     if (c < d) {
         int mid = (c + d) / 2;
         cout << "mid=" << mid << endl;
         check(c, mid);
         check(mid + 1, d);
     }
}

int main() {
    // int a[12] = { 2, 3, 1, 6, 9, 112, 113, 224, 225, 226, 332, 2303 };

    check(0, 5);
    return 0;
}

Output:

C=0 D=5
mid=2
C=0 D=2
mid=1
C=0 D=1
mid=0
C=0 D=0
C=1 D=1
C=2 D=2
C=3 D=5
mid=4
C=3 D=4
mid=3
C=3 D=3
C=4 D=4
C=5 D=5

Upvotes: 0

Views: 207

Answers (1)

rcgldr
rcgldr

Reputation: 28826

Note that this is based on top down merge sort, which is popular for learning, but most libraries use a variation of bottom up merge sort instead. As far as the output goes, top down merge sort generates and pushes indexes onto the stack, resulting in a depth first, left first, ordering. No merging takes place until 2 runs of size 1 are produced. I changed the code to show the recursion level l and if the recursive call was the first one or the second one x:

#include <iostream>

using namespace std;

void check(int c, int d, int l, int x) {
    if(c >= d){
        cout << "l = " << l << "  x = " << x;
        cout << "  c = " << c << "         d = " << d << endl;
        return;
    }
    int m = (c + d) / 2;
    cout << "l = " << l << "  x = " << x;
    cout << "  c = " << c << "  m = " << m << "  d = " << d << endl;
    check(c, m, l+1, 1);
    check(m + 1, d, l+1, 2);
}

int main() {
    check(0, 5, 0, 0);
    return 0;
}

This is the output:

l = 0  x = 0  c = 0  m = 2  d = 5
l = 1  x = 1  c = 0  m = 1  d = 2
l = 2  x = 1  c = 0  m = 0  d = 1
l = 3  x = 1  c = 0         d = 0
l = 3  x = 2  c = 1         d = 1
l = 2  x = 2  c = 2         d = 2
l = 1  x = 2  c = 3  m = 4  d = 5
l = 2  x = 1  c = 3  m = 3  d = 4
l = 3  x = 1  c = 3         d = 3
l = 3  x = 2  c = 4         d = 4
l = 2  x = 2  c = 5         d = 5

Upvotes: 1

Related Questions