#include <algorithm>
template< typename Iterator>
void quick_sort(Iterator first, Iterator last) {
	if (first != last) {
		Iterator left = first;
		Iterator right = last;
		Iterator pivot = left++;
		while (left != right) {
			if (*left <= *pivot) {
				++left;
			}
			else {
				while ((left != --right) && *pivot <= *right);
				std::iter_swap(left, right);
			}
		}
		--left;
		std::iter_swap(first, left);
		quick_sort(first, left);
		quick_sort(right, last);
	}
}