Overhauled inplace_merge

algorithm

		// TEMPLATE FUNCTION inplace_merge WITH PRED
		// The "usual invariants" for the inplace_merge helpers below are:
		// [_First, _Mid) and [_Mid, _Last) are sorted
		// _Pred(*_Mid, *_First)             note: this means *_Mid is the "lowest" element
		// _Pred(*prev(_Last), *prev(_Mid))  note: this means *prev(_Mid) is the "highest" element
		// _Count1 == distance(_First, _Mid)
		// _Count2 == distance(_Mid, _Last)
		// _Count1 > 1
		// _Count2 > 1
template<class _BidIt> inline
	void _Rotate_one_right(_BidIt _First, _BidIt _Mid, _BidIt _Last)
	{	// exchanges the range [_First, _Mid) with [_Mid, _Last)
		// pre: distance(_Mid, _Last) is 1
	_Iter_value_t<_BidIt> _Temp(_STD move(*_Mid));
	_Move_backward_unchecked(_First, _Mid, _Last);
	*_First = _STD move(_Temp);
	}

template<class _BidIt> inline
	void _Rotate_one_left(_BidIt _First, _BidIt _Mid, _BidIt _Last)
	{	// exchanges the range [_First, _Mid) with [_Mid, _Last)
		// pre: distance(_First, _Mid) is 1
	_Iter_value_t<_BidIt> _Temp(_STD move(*_First));
	*_Move_unchecked(_Mid, _Last, _First) = _STD move(_Temp);
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Inplace_merge_buffer_left(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred)
	{	// move the range [_First, _Mid) to _Temp_buf, and merge it with [_Mid, _Last) to _First, using _Pred
		// usual invariants apply
	_Temporary_range<_Ty> _Temp(_Temp_buf, _First, _Mid, _Count1);
	_Ty * _Left_first = _Temp._Begin();
	_Ty * const _Left_last = _Temp._End() - 1; // avoid a compare with the highest element
	*_First = _STD move(*_Mid); // the lowest element is now in position
	++_First;
	++_Mid;
	for (;;)
		{
		if (_Pred(*_Mid, *_Left_first))
			{	// take element from the right partition
			*_First = _STD move(*_Mid);
			++_First;
			++_Mid;
			if (_Mid == _Last)
				{
				_Move_unchecked(_Left_first, _Temp._End(), _First);	// move any tail (and the highest element)
				return;
				}
			}
		else
			{	// take element from the left partition
			*_First = _STD move(*_Left_first);
			++_First;
			++_Left_first;
			if (_Left_first == _Left_last)
				{	// move the remaining right partition and highest element, since *_Left_first is highest
				*_Move_unchecked(_Mid, _Last, _First) = _STD move(*_Left_last);
				return;
				}
			}
		}
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Inplace_merge_buffer_right(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count2, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred)
	{	// move the range [_Mid, _Last) to _Temp_buf, and merge it with [_First, _Mid) to _Last, using _Pred
		// usual invariants apply
	_Temporary_range<_Ty> _Temp(_Temp_buf, _Mid, _Last, _Count2);
	*--_Last = _STD move(*--_Mid); // move the highest element into position
	_Ty * const _Right_first = _Temp._Begin();
	_Ty * _Right_last = _Temp._End() - 1;
	--_Mid;
	for (;;)
		{
		if (_Pred(*_Right_last, *_Mid))
			{	// merge from the left partition
			*--_Last = _STD move(*_Mid);
			if (_First == _Mid)
				{
				*--_Last = _STD move(*_Right_last);	// to make [_Right_first, _Right_last) a half-open range
				_Move_backward_unchecked(_Right_first, _Right_last, _Last);	// move any head (and lowest element)
				return;
				}

			--_Mid;
			}
		else
			{	// merge from the right partition
			*--_Last = _STD move(*_Right_last);
			--_Right_last;
			if (_Right_first == _Right_last)
				{	// we can't compare with *_Right_first, but we know it is lowest
				*--_Last = _STD move(*_Mid);	// restore half-open range [_First, _Mid)
				_Move_backward_unchecked(_First, _Mid, _Last);
				*_First = _STD move(*_Right_first);
				return;
				}
			}
		}
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Buffered_inplace_merge_unchecked(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Diff _Count2, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred);

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Buffered_inplace_merge_divide_and_conquer2(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Diff _Count2, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred,
		_BidIt _Firstn, _BidIt _Lastn, _Diff _Count1n, _Diff _Count2n)
	{	// common block of _Buffered_inplace_merge_divide_and_conquer, below
	_BidIt _Midn = _Buffered_rotate_unchecked(_Firstn, _Mid, _Lastn,
		_Count1 - _Count1n, _Count2n, _Temp_buf);	// rearrange middle
	_Buffered_inplace_merge_unchecked(_First, _Firstn, _Midn,
		_Count1n, _Count2n, _Temp_buf, _Pred);	// merge each new part
	_Buffered_inplace_merge_unchecked(_Midn, _Lastn, _Last,
		_Count1 - _Count1n, _Count2 - _Count2n, _Temp_buf, _Pred);
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Buffered_inplace_merge_divide_and_conquer(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Diff _Count2, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred)
	{	// merge sorted [_First, _Mid) with sorted [_Mid, _Last), using _Pred
		// usual invariants apply
	if (_Count1 <= _Count2)
		{
		const _Diff _Count1n = _Count1 >> 1;	// TRANSITION, VSO#433486
		const _BidIt _Firstn = _STD next(_First, _Count1n);
		const _BidIt _Lastn = _Lower_bound_unchecked(_Mid, _Last, *_Firstn, _Pred);
		_Buffered_inplace_merge_divide_and_conquer2(_First, _Mid, _Last, _Count1, _Count2,
			_Temp_buf, _Pred,
			_Firstn, _Lastn, _Count1n, _STD distance(_Mid, _Lastn));
		}
	else
		{
		const _Diff _Count2n = _Count2 >> 1;	// TRANSITION, VSO#433486
		const _BidIt _Lastn = _STD next(_Mid, _Count2n);
		const _BidIt _Firstn = _Upper_bound_unchecked(_First, _Mid, *_Lastn, _Pred);
		_Buffered_inplace_merge_divide_and_conquer2(_First, _Mid, _Last, _Count1, _Count2,
			_Temp_buf, _Pred,
			_Firstn, _Lastn, _STD distance(_First, _Firstn), _Count2n);
		}
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Buffered_inplace_merge_unchecked_impl(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Diff _Count2, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred)
	{	// merge sorted [_First, _Mid) with sorted [_Mid, _Last), using _Pred
		// usual invariants apply
	if (_Count1 <= _Count2 && _Count1 <= _Temp_buf._Capacity)
		{
		_Inplace_merge_buffer_left(_First, _Mid, _Last, _Count1, _Temp_buf, _Pred);
		}
	else if (_Count2 <= _Temp_buf._Capacity)
		{
		_Inplace_merge_buffer_right(_First, _Mid, _Last, _Count2, _Temp_buf, _Pred);
		}
	else
		{
		_Buffered_inplace_merge_divide_and_conquer(_First, _Mid, _Last, _Count1, _Count2, _Temp_buf, _Pred);
		}
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Buffered_inplace_merge_unchecked(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Diff _Count2, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred)
	{	// merge sorted [_First, _Mid) with sorted [_Mid, _Last), using _Pred
		// usual invariants *do not* apply; only sortedness applies
		// establish the usual invariants (explained in inplace_merge)
	if (_Mid == _Last)
		{
		return;
		}

	for (;;)
		{
		if (_First == _Mid)
			{
			return;
			}

		if (_Pred(*_Mid, *_First))
			{
			break;
			}

		++_First;
		--_Count1;
		}

	const auto _Highest = _Prev_iter(_Mid);
	do
		{
		--_Last;
		--_Count2;
		if (_Mid == _Last)
			{
			_Rotate_one_right(_First, _Mid, ++_Last);
			return;
			}
		}
	while (!_Pred(*_Last, *_Highest));

	++_Last;
	++_Count2;

	if (_Count1 == 1)
		{
		_Rotate_one_left(_First, _Mid, _Last);
		return;
		}

	_Buffered_inplace_merge_unchecked_impl(_First, _Mid, _Last, _Count1, _Count2, _Temp_buf, _Pred);
	}

template<class _BidIt,
	class _Pr> inline
	void inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last, _Pr _Pred)
	{	// merge [_First, _Mid) with [_Mid, _Last), using _Pred
	_DEBUG_RANGE(_First, _Mid);
	_DEBUG_RANGE(_Mid, _Last);
	using _UBidIt = _Unchecked_t<_BidIt>;
	auto _UFirst = _Unchecked(_First);
	auto _UMid = _Unchecked(_Mid);
	auto _ULast = _Unchecked(_Last);
	_DEBUG_ORDER_UNCHECKED(_UFirst, _UMid, _Pred);

	// establish the usual invariants:
	if (_UMid == _ULast)
		{
		return;
		}

	for (;;)
		{
		if (_UFirst == _UMid)
			{
			return;
			}

		if (_Pred(*_UMid, *_UFirst))
			{	// found that *_UMid goes in *_UFirst's position
			break;
			}

		++_UFirst;
		}

	const auto _Highest = _Prev_iter(_UMid);
	do
		{
		--_ULast;
		if (_UMid == _ULast)
			{	// rotate only element remaining in right partition to the beginning, without allocating
			_Rotate_one_right(_UFirst, _UMid, ++_ULast);
			return;
			}
		}
	while (!_Pred(*_ULast, *_Highest));	// found that *_Highest goes in *_ULast's position

	++_ULast;

	const _Iter_diff_t<_UBidIt> _Count1 = _STD distance(_UFirst, _UMid);
	if (_Count1 == 1)
		{	// rotate only element remaining in left partition to the end, without allocating
		_Rotate_one_left(_UFirst, _UMid, _ULast);
		return;
		}

	const _Iter_diff_t<_UBidIt> _Count2 = _STD distance(_UMid, _ULast);
	_Temporary_buffer<_Iter_value_t<_UBidIt>> _Temp_buf{_Min_value(_Count1, _Count2)};
	_Buffered_inplace_merge_unchecked_impl(_UFirst, _UMid, _ULast,
		_Count1, _Count2, _Temp_buf, _Pass_fn(_Pred));
	}

		// TEMPLATE FUNCTION inplace_merge
template<class _BidIt> inline
	void inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last)
	{	// merge [_First, _Mid) with [_Mid, _Last), using operator<
	_STD inplace_merge(_First, _Mid, _Last, less<>());
	}