c++ - Trying to understand merge sort program

Question

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

标签： c++mergesort

Answer 1

请注意，这是基于自顶向下合并排序，这在学习中很流行，但大多数库都使用自底向上合并排序的变体。就输出而言，自上而下的归并排序会生成索引并将其推送到堆栈上，从而形成深度优先、左优先的排序。在生成 2 次大小为 1 的运行之前，不会发生合并。我更改了代码以显示递归级别l以及递归调用是第一个还是第二个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;
}

这是输出：

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