由于STL中提供的sort算法是用在RandomAccessIterator上的，而list迭代器不具备随机访问的特性，所以对list进行排序不能使用algorithm中的sort算法，而应该使用list的成员函数sort。对list进行排序，最直接的想法就是用MergeSort，但是每次找中点就需要O(n)，可能考虑到这点，成员函数sort并没有采用这种方式实现，而是用了非递归版的MergeSort，将待归并的子序列先保存下来，感觉有点以空间换时间的意思。(由于STL中提供的sort算法是用在RandomAccessIterator上的，而list迭
阅读背景：
STL源码——list sort:归并排序的非递归实现
来源：互联网
分享到：
