囧，道理很简单，实践起来却没那么简单。因为编程语言的语言元素跟算法描述数据结构并不完全一致。
经过迭代（此处省略800字），补充上对于归并排序对于小数组采用插入排序的代码。
首先是插入排序：
1 template<typename _InIt, typename _Func>
2 void __insert_sort(_InIt first, _InIt last, _Func& Func) {
3 typedef typename iterator_traits<_InIt>::value_type _ValueType;
4
5 for (_InIt it = first + 1; it != last+1; ++it) {
6 _ValueType key = *it;
7 _InIt ite = it - 1;
8 for (; (ite - first)>=0 && !Func(*ite, key); --ite)
9 *(ite + 1) = *ite;
10 *(ite + 1) = key;
11 }
12 }
13
14 template<typename _InIt, typename _Func>
15 void insert_sort(_InIt first, _InIt last, _Func& Func) {
16 __insert_sort(first, last-1, Func);
17 }
然后是普通的归并排序：
1 template<typename _InIt, typename _Func>
2 void __merge(_InIt first, _InIt last, _Func& Func) {
3 typedef typename iterator_traits<_InIt>::value_type _ValueType;
4 vector<_ValueType> lv, rv;
5 size_t q = floor((last-first)/2);
6
7 copy(first, first+q+1, back_inserter(lv));
8 copy(first+q+1, last+1, back_inserter(rv));
9
10 typename vector<_ValueType>::iterator lit = lv.begin();
11 typename vector<_ValueType>::iterator rit = rv.begin();
12
13 _InIt it = first;
14 for (; it != last+1; ++it) {
15 if (lit == lv.end() || rit == rv.end()) break;
16 *it = Func(*lit, *rit) ? *(lit++) : *(rit++);
17 }
18
19 for(; lit != lv.end() && it != last+1; ++lit, ++it) *it = *lit;
20 for(; rit != rv.end() && it != last+1; ++rit, ++it) *it = *rit;
21 }
22
23 template<typename _InIt, typename _Func>
24 void __merge_sort(_InIt first, _InIt last, _Func& Func) {
25 if (last - first > 0) {
26 size_t q = floor((last - first)/2);
27 __merge_sort(first, first+q, Func);
28 __merge_sort(first+q+1, last, Func);
29 __merge(first, last, Func);
30 }
31 }
32
33 template<typename _InIt, typename _Func>
34 void merge_sort(_InIt first, _InIt last, _Func& Func) {
35 __merge_sort(first, last-1, Func);
36 }
归并排序中的小数组采用插入排序：
1 template<typename _InIt, typename _Func>
2 void __merge_sort(_InIt first, _InIt last, int k, _Func& Func) {
3 if (last - first > 0) {
4 int q = floor((last - first)/2);
5 if (q <= k) {
6 __insert_sort(first, last, Func);
7 } else {
8 __merge_sort(first, first+q, k, Func);
9 __merge_sort(first+q+1, last, k, Func);
10 __merge(first, last, Func);
11 }
12 }
13 }
14
15 template<typename _InIt, typename _Func>
16 void merge_sort(_InIt first, _InIt last, int k, _Func& Func) {
17 __merge_sort(first, last-1, k, Func);
18 }
测试函数：
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 #include <cassert>
5
6 using namespace std;
7
8 template<typename T>
9 void print(const vector<T>& v) {
10 for(vector<int>::const_iterator it=v.begin(); it != v.end(); it++)
11 cout << *it << " ";
12 cout << endl;
13 }
14
15 template<typename _InIt>
16 void print(_InIt first, _InIt last) {
17 for(vector<int>::const_iterator it=first; it != last; it++)
18 cout << *it << " ";
19 cout << endl;
20 }
21
22 int main() {
23 int lst[] = {1,5,2,6,3,7,4,8};
24 vector<int> v(lst, lst+8);
25
26 less<int> l;
27 insert_sort(v.begin(), v.end(), l);
28 print(v);
29
30 int lst2[] = {2,4,5,7,1,2,3,6};
31 vector<int> v2(lst2, lst2+8);
32 less_equal<int> lq;
33
34 merge_sort(v2.begin(), v2.end(), v2.size()/2, lq);
35 //merge_sort(v2.begin(), v2.end(), lq);
36 print(v2);
37
38 return 0;
39 }