#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

int count_copy_construction;
int count_move_construction;
int count_copy_assignment;
int count_move_assignment;
int count_swap;
int count_comparison;

struct A {
	std::string value;
	A() : value("") {}
	A(const A &a) : value(a.value) {
		++count_copy_construction;
	}
	A(A &&a) : value(std::move(a.value)) {
		++count_move_construction;
	}
	A &operator=(const A &a) {
		++count_copy_assignment;
		value = a.value;
		return *this;
	}
	A &operator=(A &&a) {
		++count_move_assignment;
		value = std::move(a.value);
		return *this;
	}
	bool operator<(const A &a) const {
		++count_comparison;
		return value < a.value;
	}
};
void swap(A &a, A &b) {
	++count_swap;
	std::swap(a.value, b.value);
}

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<A> 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++].value = s;
			}
			a[--last].value = s;
		}
		for (unsigned pos = first; pos < last; ++pos) {
			a[pos].value = std::string() + "z"
					+ (char)('a' + pos % 11)
					+ (char)('a' + pos % 13)
					+ (char)('a' + pos % 17)
					+ (char)('a' + pos % 19)
					+ (char)('a' + pos % 23);
		}
		count_copy_construction = 0;
		count_move_construction = 0;
		count_copy_assignment = 0;
		count_move_assignment = 0;
		count_swap = 0;
		count_comparison = 0;
		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;
		}
		std::cerr
			<< std::setw(8) << count_copy_construction << " "
			<< std::setw(8) << count_move_construction << " "
			<< std::setw(8) << count_copy_assignment << " "
			<< std::setw(8) << count_move_assignment << " "
			<< std::setw(8) << count_swap << "  "
			<< std::setw(8) << count_comparison << std::endl;
	}
	return 0;
}