本文为senlie原创，转载请保留此地址：http://blog.csdn.net/zhengsenlie

merge (应用于有序区间)

描述：将两个经过排序的集合S1和S2，合并起来置于另一段空间。所得结果也是一个有序(sorted)序列

思路：

1.遍历两个序列直到其中一个结束了

2.如果序列一的元素较小，将它放到结果序列中，并前进 1

3.如果序列二的元素较小，将它放到结果序列中，前前进 1

4.遍历结束后，将还没有遍历完的序列复制到结果序列的尾部

复杂度：O(m+n)

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result) {
  while (first1 != last1 && first2 != last2) {
    if (*first2 < *first1) {
      *result = *first2;
      ++first2;
    }
    else {
      *result = *first1;
      ++first1;
    }
    ++result;
  }
  return copy(first2, last2, copy(first1, last1, result)); // 之前一直不懂为什么 copy 之类的算法要返回一个指向 操作完后的序列的 last 的迭代器。这行代码很好地解释了原因
}

int main()
{
  int A1[] = { 1, 3, 5, 7 };
  int A2[] = { 2, 4, 6, 8 };
  const int N1 = sizeof(A1) / sizeof(int);
  const int N2 = sizeof(A2) / sizeof(int);


  merge(A1, A1 + N1, A2, A2 + N2, 
        ostream_iterator<int>(cout, " "));
  // The output is "1 2 3 4 5 6 7 8"
}