統治分割法を使っているマージソートのプログラムのわからないところ

Question

発生している問題・エラーメッセージ

統治分割法を使っているマージソートのプログラムを追っているところわからないところが出ました。
結果だけで見て７行目の[6,7,4,5,3,2,1,0]の部分から[4,5,6,7,3,2,1,0]になるのがわかりません。
（a,０、４）の関数の時
下の部分コードを見てみると
int index_left = 0;
int index_right = (int)buf.size() - 1;
index_left = 0でいいと思うのですが
int index_right は (int)buf.size() - 1となっていて要素で言うと添字３（一番はじの５）を示していると思いました。
すると、配列[５、４、６、７、3、2、1、0]になると思うのですが、[4,5,6,7,3,2,1,0]になります。
ご指摘お願いします。

前提

配列
N＝８
[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]

Comments

[episteme]

void dumpVector(vector<int>&a) を使ってvectorのナカミを確認してるんですよね?
こいつは a のナカミを「全部」プリントするんだから 8要素がプリントされてアタリマエなのでは?

[jaogjig]

修正しました。

Answer 1

[0,4)で[0,2),[3,4)の再帰をやって戻ってきた時点でa = [6,7,4,5,3,2,1,0]
ここでleft,mid,right = 0,2,4で、bufにはa[0],a[1],a[3],a[2]と積み込むんだからbuf = [6,7,5,4]。（midからrightは逆順に積んでるので、bufにおいて添え字の3は5にならない。）
bufの左右をみながらaに書き込むわけで、6vs4で4、6vs5で5、6vs7で6，最後は7vs7で7。

Comments

[jaogjig]

理解できました。ありがとうございます。