# STL源码剖析之排序（二）stable_sort

Datetime:2016-08-23 03:46:09         Topic: STL  Source Code Analysis          Share        Original >>

## 一、stable_sort算法：

• 判断[first, middle)与[middle, last)哪个区间更长，不妨设前半段区间更长
• 取[first, middle)的中点 first_cut = first + (middle – first) / 2
• 在后半段区间找到第一个大于（大于等于）first_cut值的位置 second_cut = std::lower_bound(middle, last, *first_cut)
• 区间(first_cut, second_cut)向右旋转使middle成为第一个位置 std::rotate (first_cut, middle, second_cut)
• 得到新的前后两个半区间的分界点 new_middle = first_cut + (second_cut – middle)
• 递归[first, new_middle), [new_middle, last)，重复上述步骤
• 以上只是大致算法，还要注意边界细节问题

## 二、源码剖析

stl stable_sort

```/**
*  @brief Sort the elements of a sequence, preserving the relative order
*         of equivalent elements.
*  @ingroup sorting_algorithms
*  @param  first   An iterator.
*  @param  last    Another iterator.
*  @return  Nothing.
*
*  Sorts the elements in the range @p [first,last) in ascending order,
*  such that @p *(i+1)<*i is false for each iterator @p i in the range
*  @p [first,last-1).
*
*  The relative ordering of equivalent elements is preserved, so any two
*  elements @p x and @p y in the range @p [first,last) such that
*  @p x<y is false and @p y<x is false will have the same relative
*  ordering after calling @p stable_sort().
*/
template<typename _RandomAccessIterator>
inline void
stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_DistanceType;

// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);

_Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
__last);
if (__buf.begin() == 0)
std::__inplace_stable_sort(__first, __last);
else
_DistanceType(__buf.size()));
}```

inplace_stable_sort:不需要缓冲区的归并排序，时间复杂度为O(nlog²n)。

stl __inplace_stable_sort

```/// This is a helper function for the stable sorting routines.
template<typename _RandomAccessIterator>
void
__inplace_stable_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last)
{
if (__last - __first < 15)
{
std::__insertion_sort(__first, __last);
return;
}
_RandomAccessIterator __middle = __first + (__last - __first) / 2;
std::__inplace_stable_sort(__first, __middle);
std::__inplace_stable_sort(__middle, __last);
std::__merge_without_buffer(__first, __middle, __last,
__middle - __first,
__last - __middle);
}```

merge_without_buffer采用上文中的算法进行合并，空间复杂度为O(1)

```/// This is a helper function for the merge routines.
template<typename _BidirectionalIterator, typename _Distance>
void
__merge_without_buffer(_BidirectionalIterator __first,
_BidirectionalIterator __middle,
_BidirectionalIterator __last,
_Distance __len1, _Distance __len2)
{
if (__len1 == 0 || __len2 == 0)
return;
if (__len1 + __len2 == 2)
{
if (*__middle < *__first)
std::iter_swap(__first, __middle);
return;
}
_BidirectionalIterator __first_cut = __first;
_BidirectionalIterator __second_cut = __middle;
_Distance __len11 = 0;
_Distance __len22 = 0;
if (__len1 > __len2)
{
__len11 = __len1 / 2;
__second_cut = std::lower_bound(__middle, __last, *__first_cut);
__len22 = std::distance(__middle, __second_cut);
}
else
{
__len22 = __len2 / 2;
__first_cut = std::upper_bound(__first, __middle, *__second_cut);
__len11 = std::distance(__first, __first_cut);
}
std::rotate(__first_cut, __middle, __second_cut);
_BidirectionalIterator __new_middle = __first_cut;
std::__merge_without_buffer(__first, __first_cut, __new_middle,
__len11, __len22);
std::__merge_without_buffer(__new_middle, __second_cut, __last,
__len1 - __len11, __len2 - __len22);
}```

```template<typename _RandomAccessIterator, typename _Pointer,
typename _Distance>
void
_RandomAccessIterator __last,
_Pointer __buffer, _Distance __buffer_size)
{
const _Distance __len = (__last - __first + 1) / 2;
const _RandomAccessIterator __middle = __first + __len;
if (__len > __buffer_size)
{
__buffer, __buffer_size);
__buffer, __buffer_size);
}
else
{
std::__merge_sort_with_buffer(__first, __middle, __buffer);
std::__merge_sort_with_buffer(__middle, __last, __buffer);
}
_Distance(__middle - __first),
_Distance(__last - __middle),
__buffer, __buffer_size);
}```

merge_sort_with_buffer:

mege_sort_loop: 对区间[first, last)的每个长度为step_size是子区间进行合并操作。

std::merge reference
```template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
typename _Distance>
void
__merge_sort_loop(_RandomAccessIterator1 __first,
_RandomAccessIterator1 __last,
_RandomAccessIterator2 __result,
_Distance __step_size)
{
const _Distance __two_step = 2 * __step_size;

while (__last - __first >= __two_step)
{
__result = std::merge(__first, __first + __step_size,
__first + __step_size,
__first + __two_step,
__result);
__first += __two_step;
}

__step_size = std::min(_Distance(__last - __first), __step_size);
std::merge(__first, __first + __step_size,
__first + __step_size, __last,
__result);
}

template<typename _RandomAccessIterator, typename _Distance>
void
__chunk_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Distance __chunk_size)
{
while (__last - __first >= __chunk_size)
{
std::__insertion_sort(__first, __first + __chunk_size);
__first += __chunk_size;
}
std::__insertion_sort(__first, __last);
}

enum { _S_chunk_size = 7 };

template<typename _RandomAccessIterator, typename _Pointer>
void
__merge_sort_with_buffer(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Pointer __buffer)
{
typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_Distance;

const _Distance __len = __last - __first;
const _Pointer __buffer_last = __buffer + __len;

_Distance __step_size = _S_chunk_size;
std::__chunk_insertion_sort(__first, __last, __step_size);

while (__step_size < __len)
{
std::__merge_sort_loop(__first, __last, __buffer, __step_size);
__step_size *= 2;
std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
__step_size *= 2;
}
}```

```/// This is a helper function for the merge routines.
template<typename _BidirectionalIterator, typename _Distance,
typename _Pointer>
void
_BidirectionalIterator __middle,
_BidirectionalIterator __last,
_Distance __len1, _Distance __len2,
_Pointer __buffer, _Distance __buffer_size)
{
if (__len1 <= __len2 && __len1 <= __buffer_size)
{
_Pointer __buffer_end = std::copy(__first, __middle, __buffer);
_GLIBCXX_STD_P::merge(__buffer, __buffer_end, __middle, __last,
__first);
}
else if (__len2 <= __buffer_size)
{
_Pointer __buffer_end = std::copy(__middle, __last, __buffer);
std::__merge_backward(__first, __middle, __buffer,
__buffer_end, __last);
}
else
{
_BidirectionalIterator __first_cut = __first;
_BidirectionalIterator __second_cut = __middle;
_Distance __len11 = 0;
_Distance __len22 = 0;
if (__len1 > __len2)
{
__len11 = __len1 / 2;
__second_cut = std::lower_bound(__middle, __last,
*__first_cut);
__len22 = std::distance(__middle, __second_cut);
}
else
{
__len22 = __len2 / 2;
__first_cut = std::upper_bound(__first, __middle,
*__second_cut);
__len11 = std::distance(__first, __first_cut);
}
_BidirectionalIterator __new_middle =
__len1 - __len11, __len22, __buffer,
__buffer_size);
__len22, __buffer, __buffer_size);
__len1 - __len11,
__len2 - __len22, __buffer, __buffer_size);
}
}```

__merge_backward与 std::merge 类似

```/// This is a helper function for the merge routines.
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
typename _BidirectionalIterator3>
_BidirectionalIterator3
__merge_backward(_BidirectionalIterator1 __first1,
_BidirectionalIterator1 __last1,
_BidirectionalIterator2 __first2,
_BidirectionalIterator2 __last2,
_BidirectionalIterator3 __result)
{
if (__first1 == __last1)
return std::copy_backward(__first2, __last2, __result);
if (__first2 == __last2)
return std::copy_backward(__first1, __last1, __result);
--__last1;
--__last2;
while (true)
{
if (*__last2 < *__last1)
{
*--__result = *__last1;
if (__first1 == __last1)
return std::copy_backward(__first2, ++__last2, __result);
--__last1;
}
else
{
*--__result = *__last2;
if (__first2 == __last2)
return std::copy_backward(__first1, ++__last1, __result);
--__last2;
}
}
}

/// This is a helper function for the merge routines.
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
typename _Distance>
_BidirectionalIterator1
_BidirectionalIterator1 __middle,
_BidirectionalIterator1 __last,
_Distance __len1, _Distance __len2,
_BidirectionalIterator2 __buffer,
_Distance __buffer_size)
{
_BidirectionalIterator2 __buffer_end;
if (__len1 > __len2 && __len2 <= __buffer_size)
{
__buffer_end = std::copy(__middle, __last, __buffer);
std::copy_backward(__first, __middle, __last);
return std::copy(__buffer, __buffer_end, __first);
}
else if (__len1 <= __buffer_size)
{
__buffer_end = std::copy(__first, __middle, __buffer);
std::copy(__middle, __last, __first);
return std::copy_backward(__buffer, __buffer_end, __last);
}
else
{
std::rotate(__first, __middle, __last);