マージソートのプログラムでわからないところ

Question

前提

今「問題解決力を鍛える！アルゴリズムとデータ構造」著大槻兼資の本を読んでいます。p200のマージソートのフローチャートを書いてプログラムを理解しようとしてるところわからないところが出てきました。
その部分が下の部分です。

  // 併合する
    int index_left = 0;                    // 左側の添字
    int index_right = (int)buf.size() - 1; // 右側の添字
    for (int i = left; i < right; ++i) {
        // 左側採用
        if (buf[index_left] <= buf[index_right]) {
            a[i] = buf[index_left++];
        }
        // 右側採用
        else {
            a[i] = buf[index_right--];
        }
    }

ここの部分の具体的にどこがわからないかというと
マージソート関数の再帰的に分割したまではいいのですが
マージ（統合）する時に、本書では一つ一つの要素を２、４、８とマージしています。
しかし下のコードを見ると

 int index_left = 0;                    // 左側の添字
    int index_right = (int)buf.size() - 1; // 右側の添字

一時的な配列を作ってそれぞれ変数を入れて比較するならわかりますが
やった部分mergesort(a,0,8),(4,8)(4,6)(6,8)(6,7)(7,8)...以下略
を活用しないで添字０からsize-1(7)といきなり８つの要素を合わせてソートしようとしているように見えます。
また、なぜ分割したのかがわからなくなってしまいました。
どのような手順でプログラムが動くかご教授お願いします。

要素数はN＝８
配列はa[12,9,15,3,8,17,6,1]

  // 併合する
    int index_left = 0;                    // 左側の添字
    int index_right = (int)buf.size() - 1; // 右側の添字
    for (int i = left; i < right; ++i) {
        // 左側採用
        if (buf[index_left] <= buf[index_right]) {
            a[i] = buf[index_left++];
        }
        // 右側採用
        else {
            a[i] = buf[index_right--];
        }
    }

該当のソースコード

#include <iostream>
#include <vector>
using namespace std;

// 配列 a の区間 [left, right) をソートする
// [left, right) は，left, left+1, ..., right-1 番目を表す
void MergeSort(vector<int> &a, int left, int right) {
    if (right - left == 1) return;
    int mid = left + (right - left) / 2;

    // 左半分 [left, mid) をソート
    MergeSort(a, left, mid);

    // 右半分 [mid, right) をソート
    MergeSort(a, mid, right);

    // いったん「左」と「右」のソート結果をコピーしておく (右側は左右反転)
    vector<int> buf;
    for (int i = left; i < mid; ++i) buf.push_back(a[i]);
    for (int i = right - 1; i >= mid; --i) buf.push_back(a[i]);

    // 併合する
    int index_left = 0;                    // 左側の添字
    int index_right = (int)buf.size() - 1; // 右側の添字
    for (int i = left; i < right; ++i) {
        // 左側採用
        if (buf[index_left] <= buf[index_right]) {
            a[i] = buf[index_left++];
        }
        // 右側採用
        else {
            a[i] = buf[index_right--];
        }
    }
}

int main() {
    // 入力
    int N; // 要素数
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // マージソート
    MergeSort(a, 0, N);
}

補足情報（FW/ツールのバージョンなど）

C++

Comments

[dameo]

多分再帰呼び出し的な部分が難しいのかと思います。
分割を行った後、統合を行っているのですが、分割の際に再帰呼び出しが使用されています。
再帰呼び出しから戻ってきたときには指定した範囲がソートされているので、左半分も右半分もどちらもソートされている状態で統合を行います。
参考までにコメント空行を削除して、固定データをソートするように変更した後、ちょっと出力を加えたコードを載せておきます。範囲を出力するタイミングと関数の最後で結果を出力するタイミングをよく見てください。

#include <iostream>
#include <vector>
using namespace std;
void MergeSort(vector<int> &a, int left, int right) {
if (right - left == 1) return;
cout << "[" << left << "," << right << ")" << endl;
int mid = left + (right - left) / 2;
MergeSort(a, left, mid);
MergeSort(a, mid, right);
vector<int> buf;
for (int i = left; i < mid; ++i) buf.push_back(a[i]);
for (int i = right - 1; i >= mid; --i) buf.push_back(a[i]);
int index_left = 0;
int index_right = (int)buf.size() - 1;
for (int i = left; i < right; ++i) {
if (buf[index_left] <= buf[index_right]) {
a[i] = buf[index_left++];
}
else {
a[i] = buf[index_right--];
}
}
cout << "[";
bool first = true;
for (auto v: a) {
if (first) first = false;
else cout << ",";
cout << v;
}
cout << "]" << endl;
}
int main() {
int N = 8;
vector<int> a(N);
for (int i = 0; i < N; ++i) a[i] = N - 1 - i;
MergeSort(a, 0, N);
return 0;
}

結果
[0,8)
[0,4)
[0,2)
[6,7,5,4,3,2,1,0]
[2,4)
[6,7,4,5,3,2,1,0]
[4,5,6,7,3,2,1,0]
[4,8)
[4,6)
[4,5,6,7,2,3,1,0]
[6,8)
[4,5,6,7,2,3,0,1]
[4,5,6,7,0,1,2,3]
[0,1,2,3,4,5,6,7]

[jaogjig]

配列の最初の並びはどうなっているのでしょうか

[dameo]

main関数内で
for (int i = 0; i < N; ++i) a[i] = N - 1 - i;
としているので、
[7,6,5,4,3,2,1,0]
と逆順に並べています。
前のコードを変えて出力するとこんな感じです。

#include <iostream>
#include <vector>
using namespace std;
void dumpVector(vector<int>&a) {
cout << "[";
bool first = true;
for (auto v: a) {
if (first) first = false;
else cout << ",";
cout << v;
}
cout << "]" << endl;
}
void MergeSort(vector<int> &a, int left, int right) {
if (right - left == 1) return;
cout << "[" << left << "," << right << ")" << endl;
int mid = left + (right - left) / 2;
MergeSort(a, left, mid);
MergeSort(a, mid, right);
vector<int> buf;
for (int i = left; i < mid; ++i) buf.push_back(a[i]);
for (int i = right - 1; i >= mid; --i) buf.push_back(a[i]);
int index_left = 0;
int index_right = (int)buf.size() - 1;
for (int i = left; i < right; ++i) {
if (buf[index_left] <= buf[index_right]) {
a[i] = buf[index_left++];
}
else {
a[i] = buf[index_right--];
}
}
dumpVector(a);
}
int main() {
int N = 8;
vector<int> a(N);
for (int i = 0; i < N; ++i) a[i] = N - 1 - i;
dumpVector(a);
MergeSort(a, 0, N);
return 0;
}

結果
[7,6,5,4,3,2,1,0]
[0,8)
[0,4)
[0,2)
[6,7,5,4,3,2,1,0]
[2,4)
[6,7,4,5,3,2,1,0]
[4,5,6,7,3,2,1,0]
[4,8)
[4,6)
[4,5,6,7,2,3,1,0]
[6,8)
[4,5,6,7,2,3,0,1]
[4,5,6,7,0,1,2,3]
[0,1,2,3,4,5,6,7]

[jaogjig]

分割統治法自体がわからないと思ったので少し話が逸れる可能性がありますが質問させてください
以下のコードがある場合
なぜsolve(1,2)とsolve(2,3)は3＋１で足すのでしょうか
S1＋S2が使われたからでしょうか
しかし、コードを見る限り一番最後に合計を足すだけにreturn s1 + s2;が使われているようにしか見えません。どういう理屈でそうなっているかわかりますか
分割統治法による区間の合計値の計算をしているコード
#include <iostream>
using namespace std;

int N, A[109];

int solve(int l, int r) {
if (r - l == 1) return A[l];
int m = (l + r) / 2; // 区間 [l, r) の中央で分割する
int s1 = solve(l, m); // s1 は A[l]+...+A[m-1] の合計値となる
int s2 = solve(m, r); // s2 は A[m]+...+A[r-1] の合計値となる
return s1 + s2;
}

int main() {
// 入力
cin >> N;
for (int i = 1; i <= N; i++) cin >> A[i];

// 再帰呼び出し → 答えの出力
int Answer = solve(1, N + 1);
cout << Answer << endl;
return 0;
}

[dameo]

すみませんが、流石にこれ以上どう説明したらいいのか分かりません。
初めて再帰を見ると戸惑うのは分からなくもないのですが、ロジックを順に追うだけで簡単に理解できる話かとおもいます。