#include <algorithm>
#include <string>
#include <vector>

template<typename I>
void MergeSort(I first, I last) {
	if (last - first > 1) {
		I mid = first + (last - first) / 2;
		MergeSort(first, mid);
		MergeSort(mid, last);
		std::inplace_merge(first, mid, last);
	}
}

int main() {
	for (int method = 0; method < 1; ++method) {
		std::vector<std::string> a(1000000);
		unsigned first = 0;
		unsigned last = a.size();
		for (unsigned i = 0; i < 100; ++i) {
			const std::string s = std::string()
					+ (char)('a' + i / 25)
					+ (char)('a' + i % 25);
			for (unsigned j = 0; j < i + 2; ++j) {
				a[first++] = s;
			}
			a[--last] = s;
		}
		for (unsigned pos = first; pos < last; ++pos) {
			a[pos] = std::string() + "z"
					+ (char)('a' + pos % 23);
		}
		switch (method) {
			case 0:
				std::sort(a.begin(), a.end());
				break;
			case 1:
				std::partial_sort(a.begin(), a.end(), a.end());
				break;
			case 2:
				std::stable_sort(a.begin(), a.end());
				break;
			case 3:
				MergeSort(a.begin(), a.end());
				break;
		}
	}
	return 0;
}