c++ - 试图理解归并排序程序

Question

我正在努力理解归并排序程序。为了理解我编写了这个程序但无法理解输出。如果有人解释输出，那将非常有帮助。我只理解到 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;
}

输出:

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

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