Fully optimized versions of quicksort.

quicksort.hpp

#ifndef QUICK_SORT_HPP
#define QUICK_SORT_HPP

#include <algorithm>
#include <random>

template<typename Iterator>
class QuickSort
{
public:
	
	static const std::size_t cutoff;
	
	void operator()(Iterator begin, Iterator end)
	{
		if (std::distance(begin, end) < cutoff)
		{
			_insertion_sort(begin, end);
		}
		
		else
		{
			_shuffle(begin, end);
			
			_sort(begin, end);
		}
	}
	
private:
	
	void _insertion_sort(Iterator begin, Iterator end)
	{
		if (begin == end) return;
		
		auto stop = begin;
		
		for (++begin; begin != end; ++begin)
		{
			auto value = *begin;
			
			auto j = begin, i = std::prev(begin);
			
			for ( ; i != stop && *i > value; --i, --j) *j = *i;
			
			*j = value;
		}
	}
	
	void _shuffle(Iterator begin, Iterator end)
	{
		static std::random_device seed;
		static std::mt19937 generator(seed());
		
		if (begin == end) return;
		
		std::size_t distance = 1;
		
		for (auto i = std::next(begin); i != end; ++i, ++distance)
		{
			std::uniform_int_distribution<std::size_t> distribution(0, distance);
			
			auto other = begin;
			
			std::advance(other, distribution(generator));
			
			if (i != other) std::swap(*other, *i);
		}
	}
	
	void _sort(Iterator begin, Iterator end)
	{
		if (begin == end || std::next(begin) == end) return;
		
		auto pivot = _partition(begin, end);
		
		_sort(begin, pivot);
		_sort(++pivot, end);
	}
	
	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;
	}
	
	std::pair<Iterator, Iterator> _partition3(Iterator begin, Iterator end)
	{
		auto pivot = begin++;
		
		if (pivot == end || begin == end) return {pivot, end};
		
		auto i = begin;
		
		for (--end; i != std::next(end); )
		{
			if (*i < *pivot)
			{
				if (i != begin) std::swap(*i, *begin);
				
				++i;
				++begin;
			}
			
			else if (*i > *pivot)
			{
				if (i != end) std::swap(*i, *end);
				
				--end;
			}
			
			else ++i;
		}
		
		std::swap(*pivot, *(--begin));
		
		return {begin, i};
	}
};

template<typename Iterator>
const std::size_t QuickSort<Iterator>::cutoff = 10;

template<typename Iterator>
void quick_sort(Iterator begin, Iterator end)
{
	QuickSort<Iterator> sort;
	
	sort(begin, end);
}

#endif /* QUICK_SORT_HPP */