Dual Pivot QuickSort.cpp

// Ref: http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
template<typename T>
void DualPivotQuickSort(T *lo, T *hi, const std::function<int32_t(const T &, const T&)> &cmp)
{
	auto *const hiMinus1 = hi - 1;

	if (hi - lo < 3)
	{
		if (hi != lo && cmp(*lo, *hiMinus1) > 0)
		{
			const auto t = *lo;

			*lo             = *hiMinus1;
			*hiMinus1       = t;
		}

		return;
	}

	auto p1 = *lo, p2 = *hiMinus1;

	if (p1 > p2)
	{
		const auto t = p1;

		p1 = p2;
		p2 = t;

		*lo             = p1;
		*hiMinus1       = p2;
	}

	auto a = lo, b = hiMinus1;

	for (auto i = lo + 1; i < b; )
	{
		if (cmp(*i, p1) < 0)
		{
			++a;

			const auto t = *a;

			*a = *i;
			*i = t;
			++i;
		}
		else if (cmp(*i, p2) > 0)
		{
			--b;

			const auto t = *b;

			*b = *i;
			*i = t;
		}
		else
			++i;
	}

	const auto tmp = *a;

	*a      = *lo;
	*lo     = tmp;

	const auto tmp2 = *b;

	*b              = *hiMinus1;
	*hiMinus1       = tmp2;

	DualPivotQuickSort(lo, a, cmp);
	DualPivotQuickSort(a + 1, b, cmp);
	DualPivotQuickSort(b + 1, hi, cmp);
}