Parallel Quicksort Fragment.cpp

template<class _RanIt,
	class _Pr>
	bool _Process_sort_work_item(const _RanIt _Basis, _Pr _Pred, _Sort_work_item<_RanIt>& _Wi,
		_Sort_work_item<_RanIt>& _Right_fork_wi,
		_Iter_diff_t<_RanIt>& _Work_complete) noexcept // enforces termination
	{	// processes the sort work item, _Wi, relative to _Basis
		// if the sort is divided into quicksort sub-problems:
		//   the return value is true
		//   _Wi contains the left sub-problem; the caller should continue with this
		//   _Right_fork_wi contains the right sub-problem; the caller should allow this to be stolen
		// otherwise:
		//   the return value is false
		//   _Wi's range is completely sorted
		//   _Right_fork_wi is unmodified
	using _Diff = _Iter_diff_t<_RanIt>;
	constexpr auto _Diffsort_max = static_cast<_Diff>(_ISORT_MAX);
	const auto _Size = _Wi._Size;
	const auto _First = _Basis + _Wi._Offset;
	const auto _Last = _First + _Size;
	const auto _Ideal = _Wi._Ideal;
	if (_Size <= _Diffsort_max)
		{
		_Insertion_sort_unchecked(_First, _Last, _Pred);
		_Work_complete += _Size;
		return (false);
		}

	if (0 < _Ideal)
		{	// divide and conquer by partitioning (quicksort)
		const auto _Mid = _Partition_by_median_guess_unchecked(_First, _Last, _Pred);
		const auto _New_ideal = static_cast<_Diff>((_Ideal >> 1) + (_Ideal >> 2));	// allow 1.5 log2(N) divisions
		_Wi._Size = _Mid.first - _First;
		_Wi._Ideal = _New_ideal;
		_Right_fork_wi = {_Mid.second - _Basis, _Last - _Mid.second, _New_ideal};
		_Work_complete += _Mid.second - _Mid.first;
		return (true);
		}

	// too many divisions; heap sort
	_Make_heap_unchecked(_First, _Last, _Pred);
	_Sort_heap_unchecked(_First, _Last, _Pred);
	_Work_complete += _Size;
	return (false);
	}