list::sort

才知道STL的链表也是支持排序的，当然不能用<algorithm>里的sort，而是<list>里的。而且实现的很巧妙。后来看了眼java.util.LinkedList，果然不能排序。

template <class T, class Alloc>
void list<T, Alloc>::sort() {
if (node->next == node || link_type(node->next)->next == node) return;
list<T, Alloc> carry;
list<T, Alloc> counter[64];
int fill = 0;
while (!empty()) {
carry.splice(carry.begin(), *this, begin());
int i = 0;
while(i < fill && !counter[i].empty()) {
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if (i == fill) ++fill;
}

for (int i = 1; i < fill; ++i)
counter[i].merge(counter[i-1]);
swap(counter[fill-1]);
}

貌似是分治排序，虽然有的地方说是快排。