我想我应该尝试一种展开的Ford-Johnson合并插入排序，它实现了尽可能少的比较次数(ceil(log2(6!)) = 10)并且没有交换。 不过，它没有竞争(我得到的时间比最差的排序网络解决方案sort6_sorting_network_v1稍微好一点)。

它将值加载到六个寄存器中，然后执行8到10个比较 来决定哪个720=6! 然后将寄存器写回相应的寄存器中 在这720个订单中(每种情况的代码单独)。 在最后的回写之前，没有任何交换或重新排序。我还没有查看生成的程序集代码。

static inline void sort6_ford_johnson_unrolled(int *D) {
  register int a = D[0], b = D[1], c = D[2], d = D[3], e = D[4], f = D[5];
  #define abcdef(a,b,c,d,e,f) (D[0]=a, D[1]=b, D[2]=c, D[3]=d, D[4]=e, D[5]=f)
  #define abdef_cd(a,b,c,d,e,f) (c<a ? abcdef(c,a,b,d,e,f) \
                                     : c<b ? abcdef(a,c,b,d,e,f) \
                                           : abcdef(a,b,c,d,e,f))
  #define abedf_cd(a,b,c,d,e,f) (c<b ? c<a ? abcdef(c,a,b,e,d,f) \
                                           : abcdef(a,c,b,e,d,f) \
                                     : c<e ? abcdef(a,b,c,e,d,f) \
                                           : abcdef(a,b,e,c,d,f))
  #define abdf_cd_ef(a,b,c,d,e,f) (e<b ? e<a ? abedf_cd(e,a,c,d,b,f) \
                                             : abedf_cd(a,e,c,d,b,f) \
                                       : e<d ? abedf_cd(a,b,c,d,e,f) \
                                             : abdef_cd(a,b,c,d,e,f))
  #define abd_cd_ef(a,b,c,d,e,f) (d<f ? abdf_cd_ef(a,b,c,d,e,f) \
                                      : b<f ? abdf_cd_ef(a,b,e,f,c,d) \
                                            : abdf_cd_ef(e,f,a,b,c,d))
  #define ab_cd_ef(a,b,c,d,e,f) (b<d ? abd_cd_ef(a,b,c,d,e,f) \
                                     : abd_cd_ef(c,d,a,b,e,f))
  #define ab_cd(a,b,c,d,e,f) (e<f ? ab_cd_ef(a,b,c,d,e,f) \
                                  : ab_cd_ef(a,b,c,d,f,e))
  #define ab(a,b,c,d,e,f) (c<d ? ab_cd(a,b,c,d,e,f) \
                               : ab_cd(a,b,d,c,e,f))
  a<b ? ab(a,b,c,d,e,f)
      : ab(b,a,c,d,e,f);
  #undef ab
  #undef ab_cd
  #undef ab_cd_ef
  #undef abd_cd_ef
  #undef abdf_cd_ef
  #undef abedf_cd
  #undef abdef_cd
  #undef abcdef
}

TEST(ford_johnson_unrolled,   "Unrolled Ford-Johnson Merge-Insertion sort");

This question is becoming quite old, but I actually had to solve the same problem these days: fast agorithms to sort small arrays. I thought it would be a good idea to share my knowledge. While I first started by using sorting networks, I finally managed to find other algorithms for which the total number of comparisons performed to sort every permutation of 6 values was smaller than with sorting networks, and smaller than with insertion sort. I didn't count the number of swaps; I would expect it to be roughly equivalent (maybe a bit higher sometimes).

算法sort6使用算法sort4，算法sort4使用算法sort3。下面是一些轻量级c++形式的实现(原始的模板较多，因此可以使用任何随机访问迭代器和任何合适的比较函数)。

对3个值排序

下面的算法是展开插入排序。当必须执行两次交换(6个赋值)时，它使用4个赋值:

void sort3(int* array)
{
    if (array[1] < array[0]) {
        if (array[2] < array[0]) {
            if (array[2] < array[1]) {
                std::swap(array[0], array[2]);
            } else {
                int tmp = array[0];
                array[0] = array[1];
                array[1] = array[2];
                array[2] = tmp;
            }
        } else {
            std::swap(array[0], array[1]);
        }
    } else {
        if (array[2] < array[1]) {
            if (array[2] < array[0]) {
                int tmp = array[2];
                array[2] = array[1];
                array[1] = array[0];
                array[0] = tmp;
            } else {
                std::swap(array[1], array[2]);
            }
        }
    }
}

它看起来有点复杂，因为排序对于数组的每一个可能的排列都有或多或少的一个分支，使用2~3个比较和最多4个赋值来排序三个值。

对4个值排序

这个函数调用sort3，然后对数组的最后一个元素执行展开的插入排序:

void sort4(int* array)
{
    // Sort the first 3 elements
    sort3(array);

    // Insert the 4th element with insertion sort 
    if (array[3] < array[2]) {
        std::swap(array[2], array[3]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[1] < array[0]) {
                std::swap(array[0], array[1]);
            }
        }
    }
}

该算法执行3 ~ 6次比较，最多5次交换。展开插入排序很容易，但我们将使用另一种算法进行最后一种排序…

对6个值排序

这一个使用了我称之为双插入排序的展开版本。这个名字不是很好，但很有描述性，下面是它的工作原理:

对数组中除第一个和最后一个元素外的所有元素进行排序。 如果数组的第一个元素大于最后一个元素，则交换数组的第一个元素和最后一个元素。 从前面插入第一个元素，然后从后面插入最后一个元素。

交换后，第一个元素总是比最后一个小，这意味着，当将它们插入排序序列时，在最坏的情况下，插入这两个元素的比较不会超过N次:例如，如果第一个元素已经插入到第3个位置，那么最后一个元素不能插入到第4个位置以下。

void sort6(int* array)
{
    // Sort everything but first and last elements
    sort4(array+1);

    // Switch first and last elements if needed
    if (array[5] < array[0]) {
        std::swap(array[0], array[5]);
    }

    // Insert first element from the front
    if (array[1] < array[0]) {
        std::swap(array[0], array[1]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[4] < array[3]) {
                    std::swap(array[3], array[4]);
                }
            }
        }
    }

    // Insert last element from the back
    if (array[5] < array[4]) {
        std::swap(array[4], array[5]);
        if (array[4] < array[3]) {
            std::swap(array[3], array[4]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[2] < array[1]) {
                    std::swap(array[1], array[2]);
                }
            }
        }
    }
}

我对6个值的每一次排列的测试表明，这个算法总是执行6到13个比较。我没有计算掉期的数量，但我认为在最坏的情况下它不会高于11。

我希望这能有所帮助，即使这个问题可能不再代表一个实际的问题:)

编辑:在将它放入提供的基准测试之后，它明显比大多数有趣的替代方案要慢。它的性能往往比展开插入排序好一点，但也仅此而已。基本上，它不是整数的最佳排序，但对于具有昂贵比较操作的类型可能很有趣。

//Bruteforce compute unrolled count dumbsort(min to 0-index)
void bcudc_sort6(int* a)
{
    int t[6] = {0};
    int r1,r2;

    r1=0;
    r1 += (a[0] > a[1]);
    r1 += (a[0] > a[2]);
    r1 += (a[0] > a[3]);
    r1 += (a[0] > a[4]);
    r1 += (a[0] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[0];

    r2=0;
    r2 += (a[1] > a[0]);
    r2 += (a[1] > a[2]);
    r2 += (a[1] > a[3]);
    r2 += (a[1] > a[4]);
    r2 += (a[1] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[1];

    r1=0;
    r1 += (a[2] > a[0]);
    r1 += (a[2] > a[1]);
    r1 += (a[2] > a[3]);
    r1 += (a[2] > a[4]);
    r1 += (a[2] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[2];

    r2=0;
    r2 += (a[3] > a[0]);
    r2 += (a[3] > a[1]);
    r2 += (a[3] > a[2]);
    r2 += (a[3] > a[4]);
    r2 += (a[3] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[3];

    r1=0;
    r1 += (a[4] > a[0]);
    r1 += (a[4] > a[1]);
    r1 += (a[4] > a[2]);
    r1 += (a[4] > a[3]);
    r1 += (a[4] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[4];

    r2=0;
    r2 += (a[5] > a[0]);
    r2 += (a[5] > a[1]);
    r2 += (a[5] > a[2]);
    r2 += (a[5] > a[3]);
    r2 += (a[5] > a[4]);
    while(t[r2]){r2++;} 
    t[r2] = a[5];

    a[0]=t[0];
    a[1]=t[1];
    a[2]=t[2];
    a[3]=t[3];
    a[4]=t[4];
    a[5]=t[5];
}

static __inline__ void sort6(int* a)
{
    #define wire(x,y); t = a[x] ^ a[y] ^ ( (a[x] ^ a[y]) & -(a[x] < a[y]) ); a[x] = a[x] ^ t; a[y] = a[y] ^ t;
    register int t;

    wire( 0, 1); wire( 2, 3); wire( 4, 5);
    wire( 3, 5); wire( 0, 2); wire( 1, 4);
    wire( 4, 5); wire( 2, 3); wire( 0, 1); 
    wire( 3, 4); wire( 1, 2); 
    wire( 2, 3);

    #undef wire
}

排序使用cmp==0的4个项目。 cmp的数量是~4.34 (FF原生的有~4.52)，但是比合并列表花费3倍的时间。但如果你有大数字或大文本，最好少做cmp操作。 编辑:修复bug

在线测试http://mlich.zam.slu.cz/js-sort/x-sort-x2.htm

function sort4DG(cmp,start,end,n) // sort 4
{
var n     = typeof(n)    !=='undefined' ? n   : 1;
var cmp   = typeof(cmp)  !=='undefined' ? cmp   : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end   = typeof(end)  !=='undefined' ? end   : arr[n].length;
var count = end - start;
var pos = -1;
var i = start;
var cc = [];
// stabilni?
cc[01] = cmp(arr[n][i+0],arr[n][i+1]);
cc[23] = cmp(arr[n][i+2],arr[n][i+3]);
if (cc[01]>0) {swap(n,i+0,i+1);}
if (cc[23]>0) {swap(n,i+2,i+3);}
cc[12] = cmp(arr[n][i+1],arr[n][i+2]);
if (!(cc[12]>0)) {return n;}
cc[02] = cc[01]==0 ? cc[12] : cmp(arr[n][i+0],arr[n][i+2]);
if (cc[02]>0)
    {
    swap(n,i+1,i+2); swap(n,i+0,i+1); // bubble last to top
    cc[13] = cc[23]==0 ? cc[12] : cmp(arr[n][i+1],arr[n][i+3]);
    if (cc[13]>0)
        {
        swap(n,i+2,i+3); swap(n,i+1,i+2); // bubble
        return n;
        }
    else    {
    cc[23] = cc[23]==0 ? cc[12] : (cc[01]==0 ? cc[30] : cmp(arr[n][i+2],arr[n][i+3]));  // new cc23 | c03 //repaired
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    }
else    {
    if (cc[12]>0)
        {
        swap(n,i+1,i+2);
        cc[23] = cc[23]==0 ? cc[12] : cmp(arr[n][i+2],arr[n][i+3]); // new cc23
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    else    {
        return n;
        }
    }
return n;
}

我发现至少在我的系统上，下面定义的函数sort6_iterator()和sort6_iterator_local()都运行得至少和上面的当前记录保持者一样快，而且经常明显更快:

#define MIN(x, y) (x<y?x:y)
#define MAX(x, y) (x<y?y:x)

template<class IterType> 
inline void sort6_iterator(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(*(it + x), *(it + y)); \
  const auto b = MAX(*(it + x), *(it + y)); \
  *(it + x) = a; *(it + y) = b; }

  SWAP(1, 2) SWAP(4, 5)
  SWAP(0, 2) SWAP(3, 5)
  SWAP(0, 1) SWAP(3, 4)
  SWAP(1, 4) SWAP(0, 3)
  SWAP(2, 5) SWAP(1, 3)
  SWAP(2, 4)
  SWAP(2, 3)
#undef SWAP
}

我在计时代码中给这个函数传递了std::vector的迭代器。

I suspect (from comments like this and elsewhere) that using iterators gives g++ certain assurances about what can and can't happen to the memory that the iterator refers to, which it otherwise wouldn't have and it is these assurances that allow g++ to better optimize the sorting code (e.g. with pointers, the compiler can't be sure that all pointers are pointing to different memory locations). If I remember correctly, this is also part of the reason why so many STL algorithms, such as std::sort(), generally have such obscenely good performance.

Moreover, sort6_iterator() is sometimes (again, depending on the context in which the function is called) consistently outperformed by the following sorting function, which copies the data into local variables before sorting them.1 Note that since there are only 6 local variables defined, if these local variables are primitives then they are likely never actually stored in RAM and are instead only ever stored in the CPU's registers until the end of the function call, which helps make this sorting function fast. (It also helps that the compiler knows that distinct local variables have distinct locations in memory).

template<class IterType> 
inline void sort6_iterator_local(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  const auto b = MAX(data##x, data##y); \
  data##x = a; data##y = b; }
//DD = Define Data
#define DD1(a)   auto data##a = *(it + a);
#define DD2(a,b) auto data##a = *(it + a), data##b = *(it + b);
//CB = Copy Back
#define CB(a) *(it + a) = data##a;

  DD2(1,2)    SWAP(1, 2)
  DD2(4,5)    SWAP(4, 5)
  DD1(0)      SWAP(0, 2)
  DD1(3)      SWAP(3, 5)
  SWAP(0, 1)  SWAP(3, 4)
  SWAP(1, 4)  SWAP(0, 3)   CB(0)
  SWAP(2, 5)  CB(5)
  SWAP(1, 3)  CB(1)
  SWAP(2, 4)  CB(4)
  SWAP(2, 3)  CB(2)        CB(3)
#undef CB
#undef DD2
#undef DD1
#undef SWAP
}

请注意，按如下方式定义SWAP()有时会导致稍微更好的性能，但大多数情况下会导致稍微更差的性能或性能差异可以忽略不计。

#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  data##y = MAX(data##x, data##y); \
  data##x = a; }

如果你只是想要一个排序算法，在基本数据类型上，gcc -O3始终擅长优化，无论排序函数的调用在1中出现什么上下文，然后，根据你传递输入的方式，尝试以下两种算法之一:

template<class T> inline void sort6(T it) {
#define SORT2(x,y) {if(data##x>data##y){auto a=std::move(data##y);data##y=std::move(data##x);data##x=std::move(a);}}
#define DD1(a)   register auto data##a=*(it+a);
#define DD2(a,b) register auto data##a=*(it+a);register auto data##b=*(it+b);
#define CB1(a)   *(it+a)=data##a;
#define CB2(a,b) *(it+a)=data##a;*(it+b)=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

或者如果你想通过引用传递变量，那么使用这个(下面的函数与上面的前5行不同):

template<class T> inline void sort6(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   register auto data##a=e##a;
#define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b;
#define CB1(a)   e##a=data##a;
#define CB2(a,b) e##a=data##a;e##b=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

使用register关键字的原因是，这是少数几次需要在寄存器中使用这些值的情况之一。在没有寄存器的情况下，编译器会在大多数情况下找出这个问题，但有时不会。使用register关键字可以帮助解决这个问题。但是，通常不要使用register关键字，因为它更有可能减慢代码的速度而不是加快代码的速度。

另外，注意模板的使用。这样做是有目的的，因为即使使用内联关键字，gcc对模板函数的优化通常比普通C函数要积极得多(这与gcc需要处理普通C函数的函数指针而不是模板函数有关)。

While timing various sorting functions I noticed that the context (i.e. surrounding code) in which the call to the sorting function was made had a significant impact on performance, which is likely due to the function being inlined and then optimized. For instance, if the program was sufficiently simple then there usually wasn't much of a difference in performance between passing the sorting function a pointer versus passing it an iterator; otherwise using iterators usually resulted in noticeably better performance and never (in my experience so far at least) any noticeably worse performance. I suspect that this may be because g++ can globally optimize sufficiently simple code.

如果插入排序在这里是合理的竞争，我建议尝试shell排序。我担心6个元素可能太少了，不足以跻身最佳之列，但它可能值得一试。

示例代码，未测试，未调试等。您希望调优inc = 4和inc -= 3序列以找到最优序列(例如，尝试inc = 2, inc -= 1)。

static __inline__ int sort6(int * d) {
    char j, i;
    int tmp;
    for (inc = 4; inc > 0; inc -= 3) {
        for (i = inc; i < 5; i++) {
            tmp = a[i];
            j = i;
            while (j >= inc && a[j - inc] > tmp) {
                a[j] = a[j - inc];
                j -= inc;
            }
            a[j] = tmp;
        }
    }
}

我不认为这个会赢，但是如果有人发了一个关于排序10个元素的问题，谁知道呢……

根据维基百科，这甚至可以与排序网络相结合: 普拉特，V(1979)。贝壳排序和排序网络(计算机科学杰出论文)。花环。ISBN 0-824-04406-1