Тема: Питання щодо merge sort
Знову завдання з LeetCode.
Намагаюся написати merge sort з рекурсією:
#include <iostream>
#include <vector>
void merge_array(std::vector<int> &arr, int &start, int &middle, int &end) {
const int &first_half_size = middle - start + 1;
const int &second_half_size = end - middle;
std::vector<int> first_half;
std::vector<int> second_half;
for (int i = start; i < first_half_size; ++i) {
first_half.push_back(arr.at(i));
}
for (int j = middle + 1; j < second_half_size; ++j) {
second_half.push_back(arr.at(j));
}
int index_first = 0;
int index_second = 0;
arr.clear();
while (index_first < first_half_size && index_second < second_half_size) {
if (first_half.at(index_first) <= second_half.at(index_second)) {
arr.push_back(first_half.at(index_first));
++index_first;
} else {
arr.push_back(second_half.at(index_second));
++index_second;
}
}
/*if (index_first < first_half_size) {
std::vector<int> sub_first(first_half.begin() + index_first, first_half.end());
arr.insert(arr.end(), sub_first.begin(), sub_first.end());
}
if (index_second < second_half_size) {
std::vector<int> sub_second(second_half.begin() + index_second, second_half.end());
arr.insert(arr.end(), sub_second.begin(), sub_second.end());
}*/
}
void divide_array(std::vector<int> &arr, int &start, int &end) {
if (start < end) {
int middle = start + (end - start) / 2;
divide_array(arr, start, middle);
divide_array(arr, ++middle, end);
merge_array(arr, start, middle, end);
}
}
std::vector<int> sortArray(std::vector<int> &nums) {
int start { 0 };
int end = nums.size();
divide_array(nums, start, end);
return nums;
}
int main() {
std::vector<int> nums { 5, 2, 3, 1 };
std::vector<int> sorted_array = sortArray(nums);
return 0;
}Видає помилку:
[ 50%] Building CXX object CMakeFiles/merge_sort.dir/main.cpp.o
[100%] Linking CXX executable merge_sort
terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check: __n (which is 0) >= this->size() (which is 0)
make[2]: *** [CMakeFiles/merge_sort.dir/build.make:98: merge_sort] Перервано (зроблений дамп пам'яті)
make[2]: *** Вилучаємо файл "merge_sort"
make[1]: *** [CMakeFiles/Makefile2:83: CMakeFiles/merge_sort.dir/all] Помилка 2
make: *** [Makefile:136: all] Помилка 2Розумію, що звертаюся за хибним індексом, якого не існує, але не розумію, де саме.
Чому компілятор хоча б рядка не назве, де помилка сталася?
Чи є якесь розширення для С++, яке виводитиме помилки більш деталізовано й зрозуміло для звичайної людини?
