stable_partition 如何成为自适应算法？

stable_partition是c++ STL算法头文件中的函数模板。 我读到它是一种自适应算法，其时间复杂度为 O(n*logn) 或 O(n)，具体取决于某些因素。有人可以解释一下这些因素是什么以及时间复杂度如何取决于这些因素。谢谢 ！

有2 实施.

1. “慢点”O(n*logn)执行
2. “快点”O(n)执行

The fast但实施需要使用大量内存，这可能不可用。所以stable_partition询问操作系统是否有足够的可用内存，然后在两种实现之间进行选择。

这是一个来自海湾合作委员会 4.8.1 实施附上我的一些评论：

template<typename _ForwardIterator, typename _Predicate>
    _ForwardIterator
    stable_partition(_ForwardIterator __first, _ForwardIterator __last,
             _Predicate __pred)
    {
       ...
       ...

       /// Try to allocate enough memory for the faster algorithm
      _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last);

    if (__buf.size() > 0)  /// If there is enough memory
      return
        std::__stable_partition_adaptive(__first, __last, __pred,
                      _DistanceType(__buf.requested_size()),
                      __buf.begin(),
                      _DistanceType(__buf.size()));
    else  /// If there is not enough memory
      return
        std::__inplace_stable_partition(__first, __pred,
                     _DistanceType(__buf.requested_size()));
    }

here std::__stable_partition_adaptive是快速算法并且std::__inplace_stable_partition是慢算法。