Hopefully finally edge-case-secure partitioning algorithm.

partition.cpp

template<typename Iterator>
Iterator partition(Iterator begin, Iterator end)
{
	auto pivot = begin++;
	
	if (pivot == end || begin == end) return pivot;
	
	for (--end; begin != end; ++begin)
	{
		while (begin != end && *begin < *pivot) ++begin;
		
		while (begin != end && *end > *pivot) --end;
		
		if (begin == end) break;
		
		std::swap(*begin, *end);
	}
	
	if (*begin > *pivot) --begin;
	
	std::swap(*begin, *pivot);
	
	return begin;
}