An implementation of merge sort.

merge_sort.cpp

#include <iostream>
#include <vector>

using namespace std;

template <class T>
void merge_two_sorted_arrays(int low, int high, int mid, vector<T> &input_array) {
	vector<T> partial_array;
	int m = low, n = mid + 1;
	while (m <= mid && n <= high) {
		if (input_array[m] <= input_array[n]) {
			partial_array.push_back(input_array[m]);
			m++;
		}
		else {
			partial_array.push_back(input_array[n]);
			n++;
		}
	}
	if(m <= mid)
		partial_array.insert(partial_array.end(), input_array.begin() + m, input_array.end());
	else
		partial_array.insert(partial_array.end(), input_array.begin() + n, input_array.end());
	
	for (int i = low; i <= high; i++)
		input_array[i] = partial_array[i - low];
}

template <class T>
void merge_sort(int low, int high, vector<T> &input_array) {
	if (low != high) {
		int mid = (low + high) / 2;
		merge_sort(low, mid, input_array);
		merge_sort(mid + 1, high, input_array);
		merge_two_sorted_arrays(low, high, mid, input_array);
	}
}

void main() {
	vector<int> my_array;
	int number;
	do {
		cin >> number;
		my_array.push_back(number);
	} while (cin.get() != '\n');
	merge_sort(0, my_array.size() - 1, my_array);
	for (auto i : my_array)
		cout << i << ' ';

	cin.get();
}