二路归并

如果内存充足，可以考虑使用非原地的归并排序获得更快的速度。非原地的归并排序算法空间复杂度为O(n)，时间复杂度O(nlogn)。它的核心是归并，下面看看归并的基本实现过程。

待排序序列：

52, 50, 50, 74, 61, 46, 84, 85, 73, 23, 94, 53, 97, 98, 65, 87, 29, 13, 61, 58, 19

可以把上面的无序序列分成四段并对各段进行插入排序，得到四个有序子序列：

46, 50, 50, 52, 61, 74, 84, 23, 73, 85, 94, 13, 29, 53, 65, 87, 97, 98, 19, 58, 61

两两归并成一段，得到两个有序子序列：

23, 46, 50, 50, 52, 61, 73, 74, 84, 85, 94, 13, 19, 29, 53, 58, 61, 65, 87, 97, 98

归并成一个有序序列，排序完成。

13, 19, 23, 29, 46, 50, 50, 52, 53, 58, 61, 61, 65, 73, 74, 84, 85, 87, 94, 97, 98

  1 template <typename InputIterator, typename OutputIterator, typename Compare>
  2 OutputIterator merge(InputIterator first1, InputIterator last1, InputIterator first2,
  3                      InputIterator last2, OutputIterator result, Compare cmp)
  4 {
  5   while(first1 != last1 && first2 != last2)
  6   {
  7     if(cmp(*first2, *first1))
  8     {
  9       *result = *first2;
 10       ++first2;
 11     }
 12     else
 13     {
 14       *result = *first1;
 15       ++first1;
 16     }
 17     ++result;
 18   }
 19   return copy(first2, last2, copy(first1, last1, result));
 20 }
 21 
 22 template <typename RandomIterator, typename Compare>
 23 void merge_sort_loop(RandomIterator first, RandomIterator last,
 24                      RandomIterator result, int step_size, Compare cmp)
 25 {
 26   int two_steps = step_size << 1;
 27   while(last - first >= two_steps)
 28   {
 29     result = merge(first, first + step_size, first + step_size,
 30                    first + two_steps, result, cmp);
 31     first += two_steps;
 32   }
 33   if(last - first < step_size)
 34     step_size = last - first;
 35   merge(first, first + step_size, first + step_size, last, result, cmp);
 36 }
 37 
 38 template <typename RandomIterator, typename Compare>
 39 void chunk_insertion(RandomIterator first, RandomIterator last,
 40                      int chunk_size, Compare cmp)
 41 {
 42   while(last - first >= chunk_size)
 43   {
 44     insertion_sort(first, first + chunk_size, cmp);
 45     first += chunk_size;
 46   }
 47   insertion_sort(first, last, cmp);
 48 }
 49 
 50 template <typename RandomIterator, typename Compare>
 51 void merge_with_buffer(RandomIterator first, RandomIterator last,
 52                        RandomIterator buffer, Compare cmp)
 53 {
 54   int len = last - first;
 55   RandomIterator buffer_last = buffer + len;
 56   int step_size = 7;
 57   chunk_insertion(first, last, step_size, cmp);
 58   while(step_size < len)
 59   {
 60     merge_sort_loop(first, last, buffer, step_size, cmp);
 61     step_size <<= 1;
 62     merge_sort_loop(buffer, buffer_last, first, step_size, cmp);
 63     step_size <<= 1;
 64   }
 65 }
 66 
 67 template <typename RandomIterator, typename Compare>
 68 RandomIterator merge_backward(RandomIterator first1, RandomIterator last1,
 69                               RandomIterator first2, RandomIterator last2,
 70                               RandomIterator result, Compare cmp)
 71 {
 72   if(first1 == last1)
 73     return copy_backward(first2, last2, result);
 74   if(first2 == last2)
 75     return copy_backward(first1, last1, result);
 76   --last1, --last2;
 77   while(true)
 78     if(cmp(*last2, *last1))
 79     {
 80       *--result = *last1;
 81       if(first1 == last1)
 82         return copy_backward(first2, ++last2, result);
 83       --last1;
 84     }
 85     else
 86     {
 87       *--result = *last2;
 88       if(first2 == last2)
 89         return copy_backward(first1, ++last1, result);
 90       --last2;
 91     }
 92 }
 93 
 94 template <typename RandomIterator, typename Compare>
 95 inline void buffered_merge_sort_adaptive(RandomIterator first, RandomIterator last,
 96                                          RandomIterator buffer, Compare cmp)
 97 {
 98   RandomIterator middle = first + ((last - first + 1) >> 1);
 99   merge_with_buffer(first, middle, buffer, cmp);
100   merge_with_buffer(middle, last, buffer, cmp);
101   int len1 = middle - first, len2 = last - middle;
102   if(len1 <= len2)
103   {
104     RandomIterator buffer_end = copy(first, middle, buffer);
105     merge(buffer, buffer_end, middle, last, first, cmp);
106   }
107   else
108   {
109     RandomIterator buffer_end = copy(middle, last, buffer);
110     merge_backward(first, middle, buffer, buffer_end, last, cmp);
111   }
112 }
113 
114 template <typename RandomIterator, typename T, typename Compare>
115 inline void buffered_merge_sort_aux(RandomIterator first, RandomIterator last, Compare cmp, T)
116 {
117   T* buf = new(std::nothrow)T[last - first];
118   if(0 != buf)
119     buffered_merge_sort_adaptive(first, last, buf, cmp);
120   delete [] buf;
121 }
122 
123 template <typename RandomIterator, typename Compare>
124 inline void buffered_merge_sort(RandomIterator first, RandomIterator last, Compare cmp)
125 {
126  if(last - first > 1)
127     buffered_merge_sort_aux(first, last, cmp, *first);
128 }