什么算法满足C++“std：：stable_sort”的复杂度要求？

根据该问题的评论者和一些进一步的阅读，之所以指定复杂性，是因为没有平凡的稳定就地 O（nlogn） 排序算法。通过对源代码的进一步检查，和 的实现是相似的，两者都是合并排序，其中就地合并的复杂度为 O（nlogn）。至于“附加内存”，这两个库需要 N 个额外的内存，其中 N 是数组的长度。libc++libstdc++

更具体地说，不是线性扫描两个子数组并一次合并一个元素，而是就地合并搜索一种方式将两个子数组中的每一个划分为两个部分（总共四个部分），这样在交换中间两个部分时，最左边两个部分中的所有元素都小于或等于最右边的两个部分。然后，他们分别在最左边和最右边的两个部分执行就地合并。