代码

const int __stl_threshold = 16;
#define value_type 
  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
    inline _BidirectionalIterator2
    copy_backward(_BidirectionalIterator1 __first,
		    _BidirectionalIterator1 __last,
		    _BidirectionalIterator2 __result)
    {
      while (__first != __last)
        *--__result = *--__last;
      return __result;
    }
  template<typename _ForwardIterator1, typename _ForwardIterator2>
    inline void
    iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
    {
      

      unsigned __tmp = *__a;
      *__a = *__b;
      *__b = __tmp;
    }
template <class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value) {
    RandomAccessIterator next = last;
    --next;
    while (value < *next) {
        *last = *next;
        last = next;
        --next;
    }
    *last = value;
}
     template <class RandomAccessIterator, class T>
    void __unguarded_insertion_sort_aux(RandomAccessIterator first, 
                                        RandomAccessIterator last, T*) {
        for (RandomAccessIterator i = first; i != last; ++i)
            __unguarded_linear_insert(i, T(*i));
    }
     
    template <class RandomAccessIterator>
    inline void __unguarded_insertion_sort(RandomAccessIterator first, 
                                    RandomAccessIterator last) {
        __unguarded_insertion_sort_aux(first, last, value_type(first));
    }
template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first, 
                            RandomAccessIterator last, T*) {
    T value = *last;
    if (value < *first) {
        copy_backward(first, last, last + 1);
        *first = value;
    }
    else
        __unguarded_linear_insert(last, value);
}
 
template <class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first == last) return; 
    for (RandomAccessIterator i = first + 1; i != last; ++i)
        __linear_insert(first, i, value_type(first));
}
  template<typename _Tp>
    inline const _Tp&
    __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
    {
      if (__a < __b)
	if (__b < __c)
	  return __b;
	else if (__a < __c)
	  return __c;
	else
	  return __a;
      else if (__a < __c)
	return __a;
      else if (__b < __c)
	return __c;
      else
	return __b;
    }
template <class RandomAccessIterator, class T>
RandomAccessIterator __unguarded_partition(RandomAccessIterator first, 
                                           RandomAccessIterator last, 
                                           T pivot) {
    while (true) {
        while (*first < pivot) ++first;
        --last;
        while (pivot < *last) --last;
        if (!(first < last)) return first;
        iter_swap(first, last);
        ++first;
    }
} 
template <class RandomAccessIterator, class T>
void __introsort_loop(RandomAccessIterator first,
                      RandomAccessIterator last, T*) {
    while (last - first > __stl_threshold) {
        RandomAccessIterator cut = __unguarded_partition
          (first, last, T(__median(*first, *(first + (last - first)/2),
                                   *(last - 1))));
        __introsort_loop(cut, last, value_type(first));
        last = cut;
    }
}
template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first, 
                            RandomAccessIterator last) {
    if (last - first > __stl_threshold) {
        __insertion_sort(first, first + __stl_threshold);
        __unguarded_insertion_sort(first + __stl_threshold, last);
    }
    else
        __insertion_sort(first, last);
}
template <class RandomAccessIterator>
inline void stdsort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first != last) {
        __introsort_loop(first, last, value_type(first));
        __final_insertion_sort(first, last);
    }
}
void sort(unsigned *a, int n) {
	stdsort(a, a + n);
}

评测结果