Выполнение сортировки слиянием и печать левой части дает мне следующий вывод для данного ввода, я не могу понять, почему он печатает 2 в конце. Пожалуйста, помогите мне с тем, как выглядят эти рекурсивные вызовы
Вход: (размер массива, а в следующей строке - массив)
5
8 5 4 2 1
и результат
8
5 8
4 5 8
2
1 2 4 5 8
вот мой полный код для справки, это очень стандартный алгоритм, поэтому просто проверьте функцию mergesort и посмотрите, что я пытаюсь напечатать.
#include <bits/stdc++.h>
using namespace std;
vector<int> merge(vector<int>&B, vector<int>&C) {
int n = B.size() + C.size();
vector<int> D(n);
for (int t{}; t < n; t++)
D[t] = 0;
int i{}, j{}, k{};
while (i < B.size() && j < C.size()) {
if (B[i] < C[j]) {
D[k] = B[i];
i++;
k++;
} else {
D[k] = C[j];
j++;
k++;
}
}
if (i < B.size()) {
while (i < B.size()) {
D[k] = B[i];
k++;
i++;
}
} else {
while (j < C.size()) {
D[k] = C[j];
k++;
j++;
}
}
return D;
}
vector<int> merge_sort(vector<int> &A, int left, int right) {
vector <int> B, C, A_;
if (left == right) {
A_.push_back(A[left]);
return A_;
}
int m = (left + right) / 2; //possible error, convert this to int then
B = merge_sort(A, left, m);
for (int i{}; i < B.size(); i++)
cout << B[i] << " ";
cout << endl;
C = merge_sort(A, m + 1, right);
A_ = merge(B, C);
return A_;
}
int main() {
int n;
cin >> n;
vector<int> vec(n);
for (int i{}; i < n; i++)
cin >> vec[i];
vector<int> sorted_vec = merge_sort(vec, 0, vec.size() - 1);
for (int i{}; i < n; i++)
cout << sorted_vec[i] << " ";
cout << endl;
return 0;
}