来自www.cppreference.com的文档说std::stable_sort()的复杂度为
O(n * log(n)^2)[…]。如果有额外的内存可用，那么复杂度是O(n * log(n))。
什么算法可以满足这个要求，以及指定的"额外内存"是多少?
根据对这个问题的评论和一些进一步的阅读，复杂性是这样指定的，因为没有平凡的稳定的原地O(nlogn)排序算法。通过对源代码的进一步检查，可以发现libc++和libstdc++的实现是相似的，它们都是合并排序，其中就地合并的复杂度为0 (nlogn)。至于"额外内存"，这两个库都需要N额外内存，其中N是数组的长度。
更具体地说，不是线性扫描两个子数组并一次合并一个元素，而是就地合并搜索将两个子数组分成两部分(总共四个部分)，这样当交换中间的两个部分时，最左边的两个部分中的所有元素都小于或等于最右边的两个部分。然后分别对最左边和最右边的两个部分执行就地合并。