Index: include/algorithm =================================================================== --- include/algorithm +++ include/algorithm @@ -2497,6 +2497,41 @@ template inline _LIBCPP_INLINE_VISIBILITY _ForwardIterator +__buffered__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, + typename iterator_traits<_ForwardIterator>::value_type* __buff, ptrdiff_t __buff_size) +{ + if (__first == __middle) + return __last; + if (__middle == __last) + return __first; + typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type; + typedef typename _VSTD::iterator_traits<_ForwardIterator>::difference_type difference_type; + typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type* pointer; + difference_type __len1, __len2; + __len1 = __middle - __first; + __len2 = __last - __middle; + if ((__len1 <= __buff_size) && __len1 < __len2) + { + pointer __buff_end = __move(__first, __middle, __buff); + __move(__middle, __last, __first); + return __move_backward(__buff, __buff_end, __last); + } + else if (__len2 <= __buff_size) + { + pointer __buffer_end = __move(__middle, __last, __buff); + __move_backward(__first, __middle, __last); + return __move(__buff, __buffer_end, __first); + } + else + { + return _VSTD::__rotate(__first, __middle, __last, + typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category()); + } +} + +template +inline _LIBCPP_INLINE_VISIBILITY +_ForwardIterator rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) { if (__first == __middle) @@ -4543,7 +4578,8 @@ difference_type __len22 = __len2 - __len21; // distance(__m2, __last) // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) // swap middle two partitions - __middle = _VSTD::rotate(__m1, __middle, __m2); + //__middle = _VSTD::rotate(__m1, __middle, __m2); + __middle = _VSTD::__buffered_rotate(__m1, __middle, __m2, __buff, __buff_size); // __len12 and __len21 now have swapped meanings // merge smaller range with recurisve call and larger with tail recursion elimination if (__len11 + __len21 < __len12 + __len22)