std::sort 是否也针对少量项目进行了优化？

Question

有一种算法可以在 7 次比较中对 5 个项目进行排序：设计一种有效的算法，可以在少于 8 次比较中对 5 个不同的键进行排序如果需要对 5 个项目调用该算法， 是否会std::sort()使用该算法？这个算法可以扩展到7个项目吗？在 C/C++ 中对 7 个整数进行排序最快的算法是什么？

Answer 1

查看MSVC++2013的STL中的代码std::sort，它对7项使用了插入排序。

一些评论建议使用排序网络。可以在此处生成少量项目（最多 32 个）的排序网络。特别是，对于没有并行性的 7 个项目的排序，最快的算法似乎是这个。根据这里的实验，最快的SWAP宏实现是：

#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x) 
#define SWAP(x,y) { \
    const int a = min(d[x], d[y]); \
    const int b = max(d[x], d[y]); \
    d[x] = a; d[y] = b; }

7 个项目的排序网络代码为：

template<typename T> void sort7(T* d)
{
    SWAP(0, 1);
    SWAP(2, 3);
    SWAP(0, 2);
    SWAP(1, 3);
    SWAP(1, 2);
    SWAP(4, 5);
    SWAP(4, 6);
    SWAP(5, 6);
    SWAP(0, 4);
    SWAP(1, 5);
    SWAP(1, 4);
    SWAP(2, 6);
    SWAP(3, 6);
    SWAP(2, 4);
    SWAP(3, 5);
    SWAP(3, 4);
}