STL的sort算法,为什么VC的实现选择了用3中不同的实现,而GCC只用了插入排序?
STL的sort算法，实际调用的算法不管是哪一种，都应该让算法的复杂度保持最低，对吧。
VC的sort源代码实现是，当排序的个数小于8个的时间，直接插入排序，否则用快速排序。快速排序pivot如果递归层数太深，则余下的工作采用堆排序。这样就能达到算法的最优化结果，我贴了代码:

template<class _RanIt,
class _Diff,
class _Pr> inline
void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
{// order [_First, _Last), using _Pred
_Diff _Count;
for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
{// divide and conquer by quicksort
_STD pair<_RanIt, _RanIt> _Mid =
_Unguarded_partition(_First, _Last, _Pred);
_Ideal /= 2, _Ideal += _Ideal / 2;// allow 1.5 log2(N) divisions

if (_Mid.first - _First < _Last - _Mid.second)
{// loop on second half
_Sort(_First, _Mid.first, _Ideal, _Pred);
_First = _Mid.second;
}
else
{// loop on first half
_Sort(_Mid.second, _Last, _Ideal, _Pred);
_Last = _Mid.first;
}
}

if (_ISORT_MAX < _Count)
{// heap sort if too many divisions
_STD make_heap(_First, _Last, _Pred);
_STD sort_heap(_First, _Last, _Pred);
}
else if (1 < _Count)
_Insertion_sort(_First, _Last, _Pred);// small
}

但是GCC4.4里面的源代码，我看起来都是插入排序啊:

  template<typename _RandomAccessIterator>
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;

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

      if (__first != __last)
{
  std::__introsort_loop(__first, __last,
std::__lg(__last - __first) * 2);
  std::__final_insertion_sort(__first, __last); 
 
}
    }

以及

  /// This is a helper function for the sort routine.
  template<typename _RandomAccessIterator>
    void
    __final_insertion_sort(_RandomAccessIterator __first,
   _RandomAccessIterator __last)
    {
      if (__last - __first > int(_S_threshold))
{
  std::__insertion_sort(__first, __first + int(_S_threshold));
  std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
}
      else
std::__insertion_sort(__first, __last);
    }

这岂不是会让sort算法的复杂度保持在o(n^2)? GCC的STL实现不该回这么傻吧
[解决办法]
__introsort_loop是啥？
[解决办法]
introsort不是insert sort。introsort是小数据量用堆排序的快速排序。
而且标准有规定sort的复杂度必须是期望O(nlogn)。