c - 分类网络如何击败通用分类算法？

关于fastest sort of fixed length 6 int array，我不完全理解这个sorting network如何胜过像insertion sort这样的算法。
从这个问题来看，这里是完成排序所需CPU周期数的比较：
Linux 32位，GCC4.4.1，英特尔酷睿2四核Q8300，-O2
插入排序（daniel stutzbach）：1425
排序网络（daniel stutzbach）：1080
使用的代码如下：
插入排序（daniel stutzbach）

static inline void sort6_insertion_sort_v2(int *d){
    int i, j;
    for (i = 1; i < 6; i++) {
            int tmp = d[i];
            for (j = i; j >= 1 && tmp < d[j-1]; j--)
                    d[j] = d[j-1];
            d[j] = tmp;
    }
}

分类网络（丹尼尔·斯图茨巴赫）

static inline void sort6_sorting_network_v1(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
    SWAP(1, 2);
    SWAP(0, 2);
    SWAP(0, 1);
    SWAP(4, 5);
    SWAP(3, 5);
    SWAP(3, 4);
    SWAP(0, 3);
    SWAP(1, 4);
    SWAP(2, 5);
    SWAP(2, 4);
    SWAP(1, 3);
    SWAP(2, 3);
#undef SWAP
}

我知道排序网络非常适合并行排序，因为有些步骤独立于其他步骤。但这里我们没有使用并行化。
我希望它更快，因为它的优点是预先知道元素的确切数量。插入排序究竟在哪里以及为什么进行不必要的比较？
编辑1：
这是将这些代码与以下代码进行比较的输入集：

int d[6][6] = {\
    {1, 2, 3, 4, 5, 6},\
    {6, 5, 4, 3, 2, 1},\
    {100, 2, 300, 4, 500, 6},\
    {100, 2, 3, 4, 500, 6},\
    {1, 200, 3, 4, 5, 600},\
    {1, 1, 2, 1, 2, 1}\
};\

最佳答案

但这里我们没有使用并行化。
现代的cpu可以计算出指令何时是独立的，并将并行执行它们。因此，即使只有一个线程，也可以利用排序网络的并行性。
插入排序究竟在哪里进行不必要的比较？
查看额外比较的最简单方法是手工做一个示例。

Insertion sort:
6 5 4 3 2 1
5 6 4 3 2 1
5 4 6 3 2 1
4 5 6 3 2 1
4 5 3 6 2 1
4 3 5 6 2 1
3 4 5 6 2 1
3 4 5 2 6 1
3 4 2 5 6 1
3 2 4 5 6 1
2 3 4 5 6 1
2 3 4 5 1 6
2 3 4 1 5 6
2 3 1 4 5 6
2 1 3 4 5 6
1 2 3 4 5 6

Sorting network:
6 5 4 3 2 1
6 4 5 3 2 1
5 4 6 3 2 1
4 5 6 3 2 1 # These three can execute in parallel with the first three
4 5 6 3 1 2 #
4 5 6 2 1 3 #
4 5 6 1 2 3
1 5 6 4 2 3
1 2 6 4 5 3
1 2 3 4 5 6
1 2 3 4 5 6

关于c - 分类网络如何击败通用分类算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3901079/