我正在尝试编写合并排序算法的实现。但是我不明白如何正确使用内存。这是我的代码:
void merge(vector<int>::iterator begin1, vector<int>::iterator end1,
vector<int>::iterator begin2, vector<int>::iterator end2,
vector<int>::iterator out) {
while (begin1 != end1) {
if (*begin1 <= * begin2 || begin2 == end2) {
*out++ = *begin1++;
} else {
*out++ = *begin2++;
}
}
while (begin1 < end1) {
*out++ = *begin1++;
}
while (begin2 < end2) {
*out++ = *begin2++;
}
}
void merge_sort(vector<int> &v) {
unsigned long n = v.size();
if (n == 1) {
return;
}
vector<int> v1;
v1.assign(v.begin(), v.begin() + n/2);
vector<int> v2;
v2.assign(v.begin() + n/2, v.end());
merge_sort(v1);
merge_sort(v2);
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v.begin());
v1.clear();
v2.clear();
}
它可以工作,但它不能有效地使用内存。我该如何改进它?
STL 可以使用 std::inplace_merge 以低内存占用执行merge_sort,例如http://en.cppreference.com/w/cpp/algorithm/inplace_merge
下面是有关如何完成就地合并的高级说明:STL__merge_without_buffer算法?