//输出结果
template<class T>
void PrintVecResult(vector<T>& vec)
{
  cout << "vector result:" << endl;
  int i = 0;
  for (i = 0; i < vec.size(); i++)
  {
    cout << vec[i] << endl;
  }
  cout << "vec end" << endl;
}

//最快合并两个有序数组
//时间复杂度vec_one.size() + vec_two.size()
template<class T>
vector<T>& MergeVector(vector<T>& vec_one,vector<T>& vec_two)
{
  vector<T> vec_merge;
  vec_merge.reserve(122); //分配两个数组最大
  int i = 0; //for one
  int j = 0; // for two
  int k = 0;
  int v1_count = vec_one.size();
  int v2_count = vec_two.size();
  int v_merge_count = v1_count+ v2_count;
  //  int k = 0;
  while (i < v1_count && j < v2_count)
  {
    //如果第一项 小于 第二项
    if (vec_one[i] < vec_two[j])
    {
      vec_merge.push_back(vec_one[i]);
      i = i+1;
    }
    else
    {
      vec_merge.push_back(vec_two[j]); //从小到大排序
      j = j+1;
    }
  }
  //至少会排完一列，剩下判断
  while (i < v1_count)
  {
    vec_merge.push_back(vec_one[i++]);
  }
  while (j < v2_count)
  {
    vec_merge.push_back(vec_two[j++]);
  }


  PrintVecResult(vec_merge);
  return vec_merge;
}

int _tmain(int argc, _TCHAR* argv[])
{
  vector<int> mm;
  mm.push_back(11);
  mm.push_back(12);

  mm.push_back(21);
  mm.push_back(32);
  vector<int> ff;
  ff.push_back(1);
  ff.push_back(6);

  ff.push_back(211);
  ff.push_back(322);
  MergeVector(mm,ff);
  system("pause");

  return 0;
}