#pragma warning (disable:4786) 
#include <iostream> 
#include <vector> 
#include <string> 
using namespace std; 
template <typename T> 
void merge(vector<T>& v, int first, int mid, int last) 
{ 
vector<T> tempVector; 
int indexA, indexB, indexV; 
indexA = first; 
indexB = mid; 
 
while (indexA<mid && indexB<last) 
{ 
   if (v[indexA] < v[indexB]) 
   { 
    tempVector.push_back(v[indexA]); 
    indexA++; 
   } 
<else 
   { 
    tempVector.push_back(v[indexB]); 
    indexB++; 
   } 
} 
 
while (indexA < mid) 
{ 
   tempVector.push_back(v[indexA]); 
   indexA++; 
} 
while (indexB < last) 
{ 
   tempVector.push_back(v[indexB]); 
   indexB++; 
} 
 
indexA = first; 
for (indexV=0; indexV<tempVector.size(); indexV++) 
{ 
   v[indexA] = tempVector[indexV]; 
   indexA++; 
} 
} 
template <typename T> 
void mergeSort(vector<T>& v, int first, int last) 
{ 
if (first + 1 <last) 
{ 
   int midpt = (last+first)/2; 
 
   mergeSort(v, first, midpt); 
   mergeSort(v, midpt, last); 
   merge(v, first, midpt, last); 
} 
} 
int main() 
{ 
int intList[] = {25, 10, 7, 19, 3, 48, 12, 17, 56, 30, 21}; 
string strList[] = {"Dallas", "Akron", "Wausau", "Phoenix", "Fairbanks", "Miami"}; 
vector<int> vIntList(intList, intList+11); 
vector<string> vStrList(strList, strList+6); 
 
mergeSort(vIntList, 0, vIntList.size()); 
cout<< "Sorted integers: "; 
int i; 
for (i=0; i<vIntList.size(); i++) 
   cout<<vIntList[i]<<" "; 
cout<<endl; 
mergeSort(vStrList, 0, vStrList.size()); 
cout<< "Sorted strings: "; 
for (i=0; i<vStrList.size(); i++) 
   cout<<vStrList[i]<<" "; 
cout<<endl; 
return 0; 
}