您应该使用std::distance
, std::next
(或 c++03 中的 std::advance )进行计算。
此外,硬编码vector
与使其通用,IYAM完全相反
template<typename It>
void Merge_Sort(It begin, It end) {
size_t length = std::distance(begin, end);
if (1 >= length) return;
size_t mid = length/2;
auto pivot = std::next(begin, mid);
Merge_Sort(begin, pivot);
Merge_Sort(pivot, end);
inplace_merge(begin, pivot, end);
}
为了完整起见,这里有一个集成了比较谓词并在 Coliru 上按降序排序的
#include <algorithm>
#include <vector>
#include <iterator>
template<typename It,
typename Cmp = typename std::less<typename std::iterator_traits<It>::value_type> >
void Merge_Sort(It begin, It end, Cmp cmp = Cmp()) {
size_t length = std::distance(begin, end);
if (length<2) return;
size_t mid = length/2;
auto pivot = std::next(begin, mid);
Merge_Sort(begin, pivot, cmp);
Merge_Sort(pivot, end, cmp);
std::inplace_merge(begin, pivot, end, cmp);
}
#include <iostream>
int main()
{
std::vector<int> v { 1,3,7,-3,4,99,-13 };
Merge_Sort(begin(v), end(v), std::greater<int>());
for(auto i : v)
std::cout << i << " ";
}