template<typename Iterator>
void InsertionSort(Iterator begin, Iterator end) {
    if (begin == end) return;
    for(auto it=begin;it!=end;++it){
        std::rotate(std::upper_bound(begin,it,*it),it,std::next(it));//upper_bound在[begin,it)二分查找第一个大于*it
    }

819msAC。插排的二分优化不是减小常数的吗。还是这个rotate函数是常数世间的