template <class T>
void mergeSort(vector<T>& s) { mergeHelper(s.begin(), 0, s.size()); }
 
 
template <class Itr>
void mergeHelper(Itr start, unsigned int low, unsigned int high) {
 
	// If current element is the only element in the vector, return the element
	if (low + 1 == high) return;
 
	// Find the center of the current vector
	unsigned int center = ((high + low) / 2);
 
	// Sort lower half  
	mergeHelper(start, low, center);
 
	// Sort upper half
	mergeHelper(start, center, high);
 
	// Combine consecutive sorted ranges [first, middle) and [middle, last) 
	// into a single sorted range [first, last)  
	inplace_merge(start + low, start + center, start + high);
}

template <class T>
void mergeSort(vector<T>& s) { 
	vector<T>* temp = new vector<T>(s.size());
	if(temp != NULL) { mergeHelper(s.begin(), 0, s.size(), temp->begin()); }
	delete temp;
}
 
 
template <class T>
T max(int x, int y) {
	if(x > y) { return x; }
    else { return y; }
}
 
 
template <class Itr>
void mergeHelper(Itr start, unsigned int low, unsigned int high, Itr temp) {
	if (low + 1 == high) return;
	else {
		unsigned int center = ((high + low) / 2);
		int l = low;
		int h = center;
 
		mergeHelper(start, low, center, temp);
		mergeHelper(start, center, high, temp);
 
		for(int i = 0; i < (high - low); i++) {
			if (l < center && (h == high || max(start[l], start[h]) == start[h])) {
				temp[i] = start[l];
				l++;
			}
			else {
				temp[i] = start[h];
				h++;
			}
		}
 
		for(i = low; i < high; i++) { start[i] = temp[i - low]; }
	}
}