Aquí está una implementación usando redes de ordenación :

inline void Sort2(int *p0, int *p1)
{
    const int temp = min(*p0, *p1);
    *p1 = max(*p0, *p1);
    *p0 = temp;
}

inline void Sort3(int *p0, int *p1, int *p2)
{
    Sort2(p0, p1);
    Sort2(p1, p2);
    Sort2(p0, p1);
}

inline void Sort4(int *p0, int *p1, int *p2, int *p3)
{
    Sort2(p0, p1);
    Sort2(p2, p3);
    Sort2(p0, p2);  
    Sort2(p1, p3);  
    Sort2(p1, p2);  
}

inline void Sort6(int *p0, int *p1, int *p2, int *p3, int *p4, int *p5)
{
    Sort3(p0, p1, p2);
    Sort3(p3, p4, p5);
    Sort2(p0, p3);  
    Sort2(p2, p5);  
    Sort4(p1, p2, p3, p4);  
}

Realmente necesita implementaciones sin ramas min y max muy eficientes para esto, ya que eso es efectivamente a lo que se reduce este código: una secuencia de operaciones min y max (13 de cada una, en total). Dejo esto como un ejercicio para el lector.

Tenga en cuenta que esta implementación se presta fácilmente a la vectorización (por ejemplo, SIMD-la mayoría de las ISA de SIMD tienen instrucciones vectoriales min / max) y también a la GPU implementaciones (por ejemplo, CUDA-siendo sin ramas no hay problemas con la divergencia de urdimbre, etc.).

Ver también: Implementación rápida de algoritmos para ordenar listas muy pequeñas

Dado que estos son enteros y las comparaciones son rápidas, ¿por qué no calcular el orden de rango de cada uno directamente:

inline void sort6(int *d) {
  int e[6];
  memcpy(e,d,6*sizeof(int));
  int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]);
  int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]);
  int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]);
  int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]);
  int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]);
  int o5 = 15-(o0+o1+o2+o3+o4);
  d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];
}

Parece que llegué a la fiesta un año tarde, pero aquí vamos...

Mirando el ensamblado generado por gcc 4.5.2 observé que se están realizando cargas y almacenes para cada intercambio, lo cual realmente no es necesario. Sería mejor cargar los 6 valores en registros, ordenarlos y almacenarlos de nuevo en la memoria. Ordené que las cargas en las tiendas estuvieran lo más cerca posible de allí. Primero se necesitan los registros y se usan por última vez. También usé la macro de SWAP de Steinar H. Gunderson. Actualización: Cambié a Macro de intercambio de Paolo Bonzini que gcc convierte en algo similar a Gunderson, pero gcc es capaz de ordenar mejor las instrucciones ya que no se dan como ensamblaje explícito.

Utilicé la misma orden de swap que la red de swap reordenada dada como la de mejor rendimiento, aunque puede haber una mejor orden. Si encuentro un poco más de tiempo voy a generar y probar un montón de permutaciones.

Cambié el código de prueba para considerar más de 4000 matrices y mostrar el número promedio de ciclos necesitaba ordenar cada uno. En un i5 - 650 estoy obteniendo ~34.1 ciclos/ordenación (usando-O3), en comparación con la red de ordenación reordenada original obteniendo ~65.3 ciclos/ordenación (usando-O1, beats-O2 y-O3).

#include <stdio.h>

static inline void sort6_fast(int * d) {
#define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; }
    register int x0,x1,x2,x3,x4,x5;
    x1 = d[1];
    x2 = d[2];
    SWAP(x1, x2);
    x4 = d[4];
    x5 = d[5];
    SWAP(x4, x5);
    x0 = d[0];
    SWAP(x0, x2);
    x3 = d[3];
    SWAP(x3, x5);
    SWAP(x0, x1);
    SWAP(x3, x4);
    SWAP(x1, x4);
    SWAP(x0, x3);
    d[0] = x0;
    SWAP(x2, x5);
    d[5] = x5;
    SWAP(x1, x3);
    d[1] = x1;
    SWAP(x2, x4);
    d[4] = x4;
    SWAP(x2, x3);
    d[2] = x2;
    d[3] = x3;

#undef SWAP
#undef min
#undef max
}

static __inline__ unsigned long long rdtsc(void)
{
    unsigned long long int x;
    __asm__ volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
    return x;
}

void ran_fill(int n, int *a) {
    static int seed = 76521;
    while (n--) *a++ = (seed = seed *1812433253 + 12345);
}

#define NTESTS 4096
int main() {
    int i;
    int d[6*NTESTS];
    ran_fill(6*NTESTS, d);

    unsigned long long cycles = rdtsc();
    for (i = 0; i < 6*NTESTS ; i+=6) {
        sort6_fast(d+i);
    }
    cycles = rdtsc() - cycles;
    printf("Time is %.2lf\n", (double)cycles/(double)NTESTS);

    for (i = 0; i < 6*NTESTS ; i+=6) {
        if (d[i+0] > d[i+1] || d[i+1] > d[i+2] || d[i+2] > d[i+3] || d[i+3] > d[i+4] || d[i+4] > d[i+5])
            printf("d%d : %d %d %d %d %d %d\n", i,
                    d[i+0], d[i+1], d[i+2],
                    d[i+3], d[i+4], d[i+5]);
    }
    return 0;
}

Cambié modifiqué el conjunto de pruebas para también reportar relojes por orden y ejecutar más pruebas (la función cmp se actualizó para manejar el desbordamiento de enteros también), aquí están los resultados en algunas arquitecturas diferentes. Intenté probar en una cpu AMD, pero rdtsc no es confiable en el X6 1100T tengo disponible.

Clarkdale (i5-650)
==================
Direct call to qsort library function      635.14   575.65   581.61   577.76   521.12
Naive implementation (insertion sort)      538.30   135.36   134.89   240.62   101.23
Insertion Sort (Daniel Stutzbach)          424.48   159.85   160.76   152.01   151.92
Insertion Sort Unrolled                    339.16   125.16   125.81   129.93   123.16
Rank Order                                 184.34   106.58   54.74    93.24    94.09
Rank Order with registers                  127.45   104.65   53.79    98.05    97.95
Sorting Networks (Daniel Stutzbach)        269.77   130.56   128.15   126.70   127.30
Sorting Networks (Paul R)                  551.64   103.20   64.57    73.68    73.51
Sorting Networks 12 with Fast Swap         321.74   61.61    63.90    67.92    67.76
Sorting Networks 12 reordered Swap         318.75   60.69    65.90    70.25    70.06
Reordered Sorting Network w/ fast swap     145.91   34.17    32.66    32.22    32.18

Kentsfield (Core 2 Quad)
========================
Direct call to qsort library function      870.01   736.39   723.39   725.48   721.85
Naive implementation (insertion sort)      503.67   174.09   182.13   284.41   191.10
Insertion Sort (Daniel Stutzbach)          345.32   152.84   157.67   151.23   150.96
Insertion Sort Unrolled                    316.20   133.03   129.86   118.96   105.06
Rank Order                                 164.37   138.32   46.29    99.87    99.81
Rank Order with registers                  115.44   116.02   44.04    116.04   116.03
Sorting Networks (Daniel Stutzbach)        230.35   114.31   119.15   110.51   111.45
Sorting Networks (Paul R)                  498.94   77.24    63.98    62.17    65.67
Sorting Networks 12 with Fast Swap         315.98   59.41    58.36    60.29    55.15
Sorting Networks 12 reordered Swap         307.67   55.78    51.48    51.67    50.74
Reordered Sorting Network w/ fast swap     149.68   31.46    30.91    31.54    31.58

Sandy Bridge (i7-2600k)
=======================
Direct call to qsort library function      559.97   451.88   464.84   491.35   458.11
Naive implementation (insertion sort)      341.15   160.26   160.45   154.40   106.54
Insertion Sort (Daniel Stutzbach)          284.17   136.74   132.69   123.85   121.77
Insertion Sort Unrolled                    239.40   110.49   114.81   110.79   117.30
Rank Order                                 114.24   76.42    45.31    36.96    36.73
Rank Order with registers                  105.09   32.31    48.54    32.51    33.29
Sorting Networks (Daniel Stutzbach)        210.56   115.68   116.69   107.05   124.08
Sorting Networks (Paul R)                  364.03   66.02    61.64    45.70    44.19
Sorting Networks 12 with Fast Swap         246.97   41.36    59.03    41.66    38.98
Sorting Networks 12 reordered Swap         235.39   38.84    47.36    38.61    37.29
Reordered Sorting Network w/ fast swap     115.58   27.23    27.75    27.25    26.54

Nehalem (Xeon E5640)
====================
Direct call to qsort library function      911.62   890.88   681.80   876.03   872.89
Naive implementation (insertion sort)      457.69   236.87   127.68   388.74   175.28
Insertion Sort (Daniel Stutzbach)          317.89   279.74   147.78   247.97   245.09
Insertion Sort Unrolled                    259.63   220.60   116.55   221.66   212.93
Rank Order                                 140.62   197.04   52.10    163.66   153.63
Rank Order with registers                  84.83    96.78    50.93    109.96   54.73
Sorting Networks (Daniel Stutzbach)        214.59   220.94   118.68   120.60   116.09
Sorting Networks (Paul R)                  459.17   163.76   56.40    61.83    58.69
Sorting Networks 12 with Fast Swap         284.58   95.01    50.66    53.19    55.47
Sorting Networks 12 reordered Swap         281.20   96.72    44.15    56.38    54.57
Reordered Sorting Network w/ fast swap     128.34   50.87    26.87    27.91    28.02

El código de prueba es bastante malo; se desborda el array inicial (¿la gente aquí no lee las advertencias del compilador?), el printf está imprimiendo los elementos incorrectos, utiliza .byte para rdtsc sin ninguna buena razón, solo hay una carrera (!), no hay nada comprobando que los resultados finales son realmente correctos (por lo que es muy fácil "optimizar" en algo sutilmente incorrecto), las pruebas incluidas son muy rudimentarias (¿no hay números negativos?) y no hay nada que impida que el compilador simplemente deseche todo funciona como código muerto.

Dicho esto, también es bastante fácil mejorar la solución de red bitonic; simplemente cambie las cosas min/max/SWAP a

#define SWAP(x,y) { int tmp; asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (d[x]), "=r" (d[y]), "=r" (tmp) : "0" (d[x]), "1" (d[y]) : "cc"); }

Y sale un 65% más rápido para mí (Debian gcc 4.4.5 con-O2, amd64, Core i7).

Me topé con esta pregunta de Google hace unos días porque también tuve la necesidad de ordenar rápidamente una matriz de longitud fija de 6 enteros. Sin embargo, en mi caso, mis enteros son solo 8 bits (en lugar de 32) y no tengo un requisito estricto de usar solo C. Pensé que compartiría mis hallazgos de todos modos, en caso de que pudieran ser útiles para alguien...

Implementé una variante de una ordenación de red en ensamblado que usa SSE para vectorizar las operaciones de comparación e intercambio, en la medida en que posible. Se necesitan seis "pasadas" para ordenar completamente la matriz. Utilicé un nuevo mecanismo para convertir directamente los resultados de PCMPGTB (vectorized compare) a parámetros de shuffle para PSHUFB (vectorized swap), usando solo un PADDB (vectorized add) y en algunos casos también una instrucción PAND (bitwise AND).

Este enfoque también tuvo el efecto secundario de producir una verdaderamente función sin ramificaciones. No hay instrucciones de salto en absoluto.

Parece que esta implementación es alrededor de un 38% más rápido que la implementación que actualmente está marcada como la opción más rápida en la pregunta ("Ordenar redes 12 con Intercambio Simple"). Modifiqué esa implementación para usar elementos de matriz char durante mis pruebas, para hacer la comparación justa.

Debo señalar que este enfoque se puede aplicar a cualquier tamaño de matriz de hasta 16 elementos. Espero que la ventaja de velocidad relativa sobre las alternativas crezca para las matrices más grandes.

El código está escrito en MASM para procesadores x86_64 con SSSE3. La función utiliza la" nueva " convención de llamadas de Windows x64. Aquí está...

PUBLIC simd_sort_6

.DATA

ALIGN 16

pass1_shuffle   OWORD   0F0E0D0C0B0A09080706040503010200h
pass1_add       OWORD   0F0E0D0C0B0A09080706050503020200h
pass2_shuffle   OWORD   0F0E0D0C0B0A09080706030405000102h
pass2_and       OWORD   00000000000000000000FE00FEFE00FEh
pass2_add       OWORD   0F0E0D0C0B0A09080706050405020102h
pass3_shuffle   OWORD   0F0E0D0C0B0A09080706020304050001h
pass3_and       OWORD   00000000000000000000FDFFFFFDFFFFh
pass3_add       OWORD   0F0E0D0C0B0A09080706050404050101h
pass4_shuffle   OWORD   0F0E0D0C0B0A09080706050100020403h
pass4_and       OWORD   0000000000000000000000FDFD00FDFDh
pass4_add       OWORD   0F0E0D0C0B0A09080706050403020403h
pass5_shuffle   OWORD   0F0E0D0C0B0A09080706050201040300h
pass5_and       OWORD 0000000000000000000000FEFEFEFE00h
pass5_add       OWORD   0F0E0D0C0B0A09080706050403040300h
pass6_shuffle   OWORD   0F0E0D0C0B0A09080706050402030100h
pass6_add       OWORD   0F0E0D0C0B0A09080706050403030100h

.CODE

simd_sort_6 PROC FRAME

    .endprolog

    ; pxor xmm4, xmm4
    ; pinsrd xmm4, dword ptr [rcx], 0
    ; pinsrb xmm4, byte ptr [rcx + 4], 4
    ; pinsrb xmm4, byte ptr [rcx + 5], 5
    ; The benchmarked 38% faster mentioned in the text was with the above slower sequence that tied up the shuffle port longer.  Same on extract
    ; avoiding pins/extrb also means we don't need SSE 4.1, but SSSE3 CPUs without SSE4.1 (e.g. Conroe/Merom) have slow pshufb.
    movd    xmm4, dword ptr [rcx]
    pinsrw  xmm4,  word ptr [rcx + 4], 2  ; word 2 = bytes 4 and 5


    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass1_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass1_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass2_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass2_and]
    paddb xmm5, oword ptr [pass2_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass3_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass3_and]
    paddb xmm5, oword ptr [pass3_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass4_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass4_and]
    paddb xmm5, oword ptr [pass4_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass5_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass5_and]
    paddb xmm5, oword ptr [pass5_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass6_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass6_add]
    pshufb xmm4, xmm5

    ;pextrd dword ptr [rcx], xmm4, 0    ; benchmarked with this
    ;pextrb byte ptr [rcx + 4], xmm4, 4 ; slower version
    ;pextrb byte ptr [rcx + 5], xmm4, 5
    movd   dword ptr [rcx], xmm4
    pextrw  word ptr [rcx + 4], xmm4, 2  ; x86 is little-endian, so this is the right order

    ret

simd_sort_6 ENDP

END

Puede compilar esto a un objeto ejecutable y vincularlo a su proyecto C. Para obtener instrucciones sobre cómo hacerlo en Visual Studio, puede leer este artículo. Puede usar el siguiente prototipo de C para llamar a la función desde su código de C:

void simd_sort_6(char *values);

Aunque me gusta mucho la macro swap proporcionada:

#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))
#define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }

Veo una mejora (que un buen compilador podría hacer):

#define SWAP(x,y) { int tmp = ((x ^ y) & -(y < x)); y ^= tmp; x ^= tmp; }

Tomamos nota de cómo funcionan min y max y extraemos la subexpresión común explícitamente. Esto elimina completamente las macros min y max.

Nunca optimice min/max sin benchmarking y mirando el ensamblaje generado por el compilador real. Si dejo que GCC optimice min con instrucciones de movimiento condicionales, obtengo una aceleración del 33%:

#define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }

(280 vs 420 ciclos en el código de prueba). ¿Con Max ?: es más o menos lo mismo, casi perdido en el ruido, pero lo anterior es un poco más rápido. Este INTERCAMBIO es más rápido con GCC y Clang.

Los compiladores también están haciendo un trabajo excepcional en la asignación de registros y el análisis de alias, mover efectivamente d [x] a variables locales por adelantado, y solo copiar de nuevo a la memoria al final. De hecho, lo hacen incluso mejor que si trabajaras completamente con variables locales (como d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5]). Estoy escribiendo esto porque estás asumiendo una fuerte optimización y sin embargo tratando de ser más astuto que el compilador en min/max. :)

Por cierto, probé Clang y GCC. Hacen la misma optimización, pero debido a las diferencias de programación los dos tienen alguna variación en los resultados, no se puede decir realmente que es más rápido o más lento. GCC es más rápido en las redes de clasificación, Clang en las clases cuadráticas.

Solo para completar, la ordenación de burbujas desenrolladas y la ordenación de inserción también son posibles. Aquí está el tipo de burbuja:

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

Y aquí está el tipo de inserción:

//#define ITER(x) { if (t < d[x]) { d[x+1] = d[x]; d[x] = t; } }
//Faster on x86, probably slower on ARM or similar:
#define ITER(x) { d[x+1] ^= t < d[x] ? d[x] ^ d[x+1] : 0; d[x] = t < d[x] ? t : d[x]; }
static inline void sort6_insertion_sort_unrolled_v2(int * d){
    int t;
    t = d[1]; ITER(0);
    t = d[2]; ITER(1); ITER(0);
    t = d[3]; ITER(2); ITER(1); ITER(0);
    t = d[4]; ITER(3); ITER(2); ITER(1); ITER(0);
    t = d[5]; ITER(4); ITER(3); ITER(2); ITER(1); ITER(0);

Esta clasificación de inserción es más rápida que la de Daniel Stutzbach, y es especialmente buena en una GPU o un equipo con predicción porque el ITER se puede hacer con solo 3 instrucciones (vs.4 para SWAP). Por ejemplo, aquí está la línea t = d[2]; ITER(1); ITER(0); en el montaje del BRAZO:

    MOV    r6, r2
    CMP    r6, r1
    MOVLT  r2, r1
    MOVLT  r1, r6
    CMP    r6, r0
    MOVLT  r1, r0
    MOVLT  r0, r6

Para seis elementos, la ordenación por inserción es competitiva con la red de ordenación (12 swaps vs.15 iteraciones equilibra 4 instrucciones/swap vs. 3 instrucciones/iteración); por supuesto, la ordenación por burbujas es más lenta. Pero no va a ser cierto cuando el tamaño crece, ya que la ordenación por inserción es O (n^2) mientras que las redes de ordenación son O(n log n).

Porté la suite de pruebas a una máquina de arquitectura PPC que no puedo identificar (no tuve que tocar el código, solo aumentar las iteraciones de la prueba, usar 8 casos de prueba para evitar contaminar los resultados con mods y reemplazar el rdtsc específico de x86):

Llamada directa a la función de biblioteca qsort : 101

Implementación ingenua (ordenación por inserción) : 299

Ordenar por inserción (Daniel Stutzbach) : 108

Tipo de inserción Desenrollada : 51

Redes de Clasificación (Daniel Stutzbach) : 26

Redes de Clasificación (Paul R) : 85

Redes de Clasificación 12 con Intercambio Rápido : 117

Ordenación de Redes 12 Intercambio reordenado : 116

Orden de Rango : 56

Un intercambio XOR puede ser útil en sus funciones de intercambio.

void xorSwap (int *x, int *y) {
     if (*x != *y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

El if puede causar demasiada divergencia en su código, pero si tiene una garantía de que todos sus ints son únicos, esto podría ser útil.

Estoy deseando probar mi mano en esto y aprender de estos ejemplos, pero primero algunos tiempos de mi 1.5 GHz PPC Powerbook G4 w/ 1 GB DDR RAM. (Tomé prestado un temporizador similar a rdtsc para PPC de http://www.mcs.anl.gov / ~kazutomo/rdtsc.html para los tiempos.) Ejecuté el programa un par de veces y los resultados absolutos variaron, pero la prueba más rápida consistentemente fue " Clasificación por inserción (Daniel Stutzbach)", con" Clasificación por inserción Desenrollada " en segundo lugar.

Aquí está el último conjunto de tiempos:

**Direct call to qsort library function** : 164
**Naive implementation (insertion sort)** : 138
**Insertion Sort (Daniel Stutzbach)**     : 85
**Insertion Sort Unrolled**               : 97
**Sorting Networks (Daniel Stutzbach)**   : 457
**Sorting Networks (Paul R)**             : 179
**Sorting Networks 12 with Fast Swap**    : 238
**Sorting Networks 12 reordered Swap**    : 236
**Rank Order**                            : 116

Aquí está mi contribución a este hilo: un shellsort optimizado de 1, 4 gap para un vector int de 6 miembros (valp) que contiene valores únicos.

void shellsort (int *valp)
{      
  int c,a,*cp,*ip=valp,*ep=valp+5;

  c=*valp;    a=*(valp+4);if (c>a) {*valp=    a;*(valp+4)=c;}
  c=*(valp+1);a=*(valp+5);if (c>a) {*(valp+1)=a;*(valp+5)=c;}

  cp=ip;    
  do
  {
    c=*cp;
    a=*(cp+1);
    do
    {
      if (c<a) break;

      *cp=a;
      *(cp+1)=c;
      cp-=1;
      c=*cp;
    } while (cp>=valp);
    ip+=1;
    cp=ip;
  } while (ip<ep);
}

En mi portátil HP dv7-3010so con un dual-core Athlon M300 @ 2 Ghz (memoria DDR2) se ejecuta en 165 ciclos de reloj. Este es un promedio calculado a partir del tiempo de cada secuencia única (6!/720 en total). Compilado para Win32 usando OpenWatcom 1.8. El bucle es esencialmente un tipo de inserción y tiene 16 instrucciones / 37 bytes de largo.

No tengo un entorno de 64 bits en el que compilar.

Si la ordenación por inserción es razonablemente competitiva aquí, recomendaría probar un shellsort. Me temo que 6 elementos es probablemente demasiado poco para estar entre los mejores, pero podría valer la pena intentarlo.

Código de ejemplo, no probado, no atracado, etc. Desea ajustar la secuencia inc = 4 e inc -= 3 para encontrar el óptimo (intente inc = 2, inc -= 1, por ejemplo).

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;
        }
    }
}

No creo que esto vaya a ganar, pero si alguien publica una pregunta sobre la clasificación de 10 elementos, que saber...

Según Wikipedia, esto incluso se puede combinar con redes de clasificación: Pratt, V (1979). Shellsort and sorting networks (Disertaciones destacadas en ciencias de la computación). Guirnalda. ISBN 0-824-04406-1

Esta pregunta se está volviendo bastante vieja, pero en realidad tuve que resolver el mismo problema en estos días: agoritmos rápidos para ordenar arreglos pequeños. Pensé que sería una buena idea compartir mis conocimientos. Mientras que primero comencé usando las redes de ordenación, finalmente logré encontrar otros algoritmos para los cuales el número total de comparaciones realizadas para ordenar cada permutación de 6 valores era menor que con las redes de ordenación, y menor que con la ordenación por inserción. No conté el número de swaps; lo haría espere que sea aproximadamente equivalente (tal vez un poco más alto a veces).

El algoritmo sort6 utiliza el algoritmo sort4 que utiliza el algoritmo sort3. Aquí está la implementación en una forma ligera de C++ (el original es pesado en plantillas para que pueda funcionar con cualquier iterador de acceso aleatorio y cualquier función de comparación adecuada).

Ordenando 3 valores

El siguiente algoritmo es una ordenación de inserción desenrollada. Cuando se tienen que realizar dos swaps (6 asignaciones), utiliza 4 asignaciones en su lugar:

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]);
            }
        }
    }
}

Parece un poco complejo porque el sort tiene más o menos una rama para cada permutación posible del array, usando 2~3 comparaciones y como máximo 4 asignaciones para ordenar los tres valores.

Ordenando 4 valores

Este llama a sort3 luego realiza una ordenación de inserción desenrollada con el último elemento del array:

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]);
            }
        }
    }
}

Este algoritmo realiza de 3 a 6 comparaciones y como máximo 5 swaps. Es fácil desenrollar una clasificación de inserción, pero lo haremos utilice otro algoritmo para la última clasificación...

Ordenando 6 valores

Este usa una versión desenrollada de lo que llamé un ordenación de inserción doble. El nombre no es tan bueno, pero es bastante descriptivo, así es como funciona:

• Ordena todo menos el primero y el último elemento del array.
• Intercambia el primero y los elementos del array si el primero es mayor que el último.
• Inserte el primer elemento en la secuencia ordenada desde el frente y luego el último elemento de la parte posterior.

Después del intercambio, el primer elemento siempre es más pequeño que el último, lo que significa que, al insertarlos en la secuencia ordenada, no habrá más de N comparaciones para insertar los dos elementos en el peor de los casos: por ejemplo, si el primer elemento se ha insertado en la 3a posición, entonces el último no se puede insertar más bajo que la 4a posición.

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]);
                }
            }
        }
    }
}

Mis pruebas en cada permutación de 6 valores muestran que este algoritmo siempre realiza entre 6 y 13 comparaciones. No calculé el número de swaps realizados, pero no espero que sea superior a 11 en el peor de los casos.

Espero que esto ayude, incluso si esta pregunta ya no representa un problema real:)

EDIT: después de ponerlo en el punto de referencia proporcionado, es cleary más lento que la mayoría de las alternativas interesantes. Tiende a funcionar un poco mejor que el tipo de inserción desenrollada, pero eso es bastante mucho. Básicamente, no es la mejor clasificación para enteros, pero podría ser interesante para tipos con una operación de comparación costosa.

Sé que llego muy tarde, pero estaba interesado en experimentar con algunas soluciones diferentes. Primero, limpié esa pasta, la hice compilar y la puse en un repositorio. Mantuve algunas soluciones indeseables como callejones sin salida para que otros no lo intentaran. Entre esta estaba mi primera solución, que intentó garantizar que x1 > x2 se calculara una vez. Después de la optimización, no es más rápido que las otras versiones simples.

He añadido una versión de bucle de orden de clasificación, ya que mi propia la aplicación de este estudio es para ordenar 2-8 ítems, por lo que dado que hay un número variable de argumentos, es necesario un bucle. Esta es también la razón por la que ignoré las soluciones de red de clasificación.

El código de prueba no comprobó que los duplicados se manejaran correctamente, así que mientras que las soluciones existentes eran todas correctas, agregué un caso especial al código de prueba para asegurar que los duplicados se manejaran correctamente.

Entonces, escribí una ordenación de inserción que está completamente en registros AVX. En mi máquina es 25% más rápido que los otros tipos de inserción, pero 100% más lento que el orden de rango. Hice esto puramente para experimentar y no tenía ninguna expectativa de que esto fuera mejor debido a la ramificación en el tipo de inserción.

static inline void sort6_insertion_sort_avx(int* d) {
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], 0, 0);
    __m256i index = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
    __m256i shlpermute = _mm256_setr_epi32(7, 0, 1, 2, 3, 4, 5, 6);
    __m256i sorted = _mm256_setr_epi32(d[0], INT_MAX, INT_MAX, INT_MAX,
            INT_MAX, INT_MAX, INT_MAX, INT_MAX);
    __m256i val, gt, permute;
    unsigned j;
     // 8 / 32 = 2^-2
#define ITER(I) \
        val = _mm256_permutevar8x32_epi32(src, _mm256_set1_epi32(I));\
        gt =  _mm256_cmpgt_epi32(sorted, val);\
        permute =  _mm256_blendv_epi8(index, shlpermute, gt);\
        j = ffs( _mm256_movemask_epi8(gt)) >> 2;\
        sorted = _mm256_blendv_epi8(_mm256_permutevar8x32_epi32(sorted, permute),\
                val, _mm256_cmpeq_epi32(index, _mm256_set1_epi32(j)))
    ITER(1);
    ITER(2);
    ITER(3);
    ITER(4);
    ITER(5);
    int x[8];
    _mm256_storeu_si256((__m256i*)x, sorted);
    d[0] = x[0]; d[1] = x[1]; d[2] = x[2]; d[3] = x[3]; d[4] = x[4]; d[5] = x[5];
#undef ITER
}

Luego, escribí un orden de clasificación usando AVX. Esto coincide con la velocidad de las otras soluciones de orden de rango, pero no es más rápido. El problema aquí es que solo puedo calcular los índices con AVX, y luego tengo que hacer una tabla de índices. Esto se debe a que el cálculo se basa en el destino en lugar de basarse en fuentes. Véase Conversión de Índices basados en la Fuente a Índices basados en el Destino

static inline void sort6_rank_order_avx(int* d) {
    __m256i ror = _mm256_setr_epi32(5, 0, 1, 2, 3, 4, 6, 7);
    __m256i one = _mm256_set1_epi32(1);
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], INT_MAX, INT_MAX);
    __m256i rot = src;
    __m256i index = _mm256_setzero_si256();
    __m256i gt, permute;
    __m256i shl = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 6, 6);
    __m256i dstIx = _mm256_setr_epi32(0,1,2,3,4,5,6,7);
    __m256i srcIx = dstIx;
    __m256i eq = one;
    __m256i rotIx = _mm256_setzero_si256();
#define INC(I)\
    rot = _mm256_permutevar8x32_epi32(rot, ror);\
    gt = _mm256_cmpgt_epi32(src, rot);\
    index = _mm256_add_epi32(index, _mm256_and_si256(gt, one));\
    index = _mm256_add_epi32(index, _mm256_and_si256(eq,\
                _mm256_cmpeq_epi32(src, rot)));\
    eq = _mm256_insert_epi32(eq, 0, I)
    INC(0);
    INC(1);
    INC(2);
    INC(3);
    INC(4);
    int e[6];
    e[0] = d[0]; e[1] = d[1]; e[2] = d[2]; e[3] = d[3]; e[4] = d[4]; e[5] = d[5];
    int i[8];
    _mm256_storeu_si256((__m256i*)i, index);
    d[i[0]] = e[0]; d[i[1]] = e[1]; d[i[2]] = e[2]; d[i[3]] = e[3]; d[i[4]] = e[4]; d[i[5]] = e[5];
}

El repositorio se puede encontrar aquí: https://github.com/eyepatchParrot/sort6 /

Creo que hay dos partes en su pregunta.

• El primero es determinar el algoritmo óptimo. Esto se hace - al menos en este caso-mediante un bucle a través de todos los pedidos posibles (no hay tantos) que le permite calcular la desviación mínima, máxima, media y estándar exacta de las comparaciones y los swaps. Tenga un finalista o dos a mano también.
• El segundo es optimizar el algoritmo. Se puede hacer mucho para convertir los ejemplos de código de libro de texto a la vida real media y magra algoritmo. Si te das cuenta de que un algoritmo no se puede optimizar en la medida necesaria, prueba con un subcampeón.

No me preocuparía demasiado por vaciar tuberías (suponiendo que la corriente x86): la predicción de ramificaciones ha recorrido un largo camino. De lo que me preocuparía es asegurarme de que el código y los datos encajen en una línea de caché cada uno (tal vez dos para el código). Una vez allí, las latencias de búsqueda son refrescantemente bajas, lo que compensará cualquier pérdida. También significa que su bucle interno será tal vez diez instrucciones más o menos, que es justo donde debería estar (hay dos bucles internos diferentes en mi algoritmo de clasificación, son 10 instrucciones/22 bytes y 9/22 de largo respectivamente). Suponiendo que el código no contiene ningún divs, puede estar seguro de que será cegadoramente rápido.

Encontré que al menos en mi sistema, las funciones sort6_iterator() y sort6_iterator_local() definidas a continuación corrían al menos tan rápido, y con frecuencia notablemente más rápido, que el titular del récord actual anterior:

#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
}

Pasé esta función un iterador std::vector en mi código de tiempo. Sospecho que el uso de iteradores le da a g++ ciertas garantías sobre lo que puede y no puede suceder a la memoria a la que se refiere el iterador, que de otra manera no tendría y son estas garantías las que permiten a g++ optimizar mejor el código de ordenación (que si no recuerdo mal, es también parte de la razón por la que tantos algoritmos std, como std::sort(), generalmente tienen un rendimiento tan obscenamente bueno). Sin embargo, mientras sincronizaba, noté que el contexto (es decir, el código circundante) en el que se realizó la llamada a la función de clasificación tuvo un impacto significativo en el rendimiento, lo que probablemente se deba a que la función está en línea y luego optimizada. Por ejemplo, si el programa era lo suficientemente simple, entonces generalmente no había gran parte de una diferencia en el rendimiento entre pasar la función de clasificación un puntero versus pasarle un iterador; de lo contrario, el uso de iteradores generalmente resultó en un rendimiento notablemente mejor y nunca (en mi experiencia hasta ahora, al menos) un rendimiento notablemente peor. Sospecho que esto puede deberse a que g++ puede optimizar globalmente el código suficientemente simple.

Además, sort6_iterator() es algunas veces (de nuevo, dependiendo del contexto en el que se llama a la función) consistentemente superado por la siguiente función de clasificación:

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
}

Tenga en cuenta que definir SWAP()de la siguiente manera algunas veces resulta en un rendimiento ligeramente mejor, aunque la mayoría de las veces resulta en un rendimiento ligeramente peor o una diferencia insignificante en el rendimiento.

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

Si solo desea un algoritmo de ordenación que gcc-O3 sea consistentemente bueno para optimizar, entonces, dependiendo de cómo pase la entrada, pruebe uno de los dos siguientes algoritmos:

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
}

O

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
}

La razón para usar la palabra clave register es porque esta es una de las pocas veces que sabe que desea estos valores en los registros. Sin register, el compilador resolverá esto la mayor parte del tiempo, pero a veces no. Usar la palabra clave register ayuda a resolver este problema. Normalmente, sin embargo, no uses la palabra clave register ya que es más probable que ralentice tu código que acelerarlo.

También, tenga en cuenta el uso de plantillas. Esto está hecho a propósito ya que, incluso con la palabra clave inline, las funciones de plantilla son generalmente mucho más agresivamente optimizadas por gcc que las funciones de vainilla C (esto tiene que ver con la necesidad de gcc de tratar con punteros de función para funciones de vainilla C pero no con funciones de plantilla).

Sé que esta es una vieja pregunta.

Pero acabo de escribir un tipo diferente de solución que quiero compartir.
Usando nada más que MIN MAX anidado,

No es rápido ya que utiliza 114 de cada uno,
podría reducirlo a 75 simplemente así - > pastebin

Pero entonces ya no es puramente min max.

Lo que podría funcionar es hacer min / max en múltiples enteros a la vez con AVX

Referencia PMINSW

#include <stdio.h>

static __inline__ int MIN(int a, int b){
int result =a;
__asm__ ("pminsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ int MAX(int a, int b){
int result = a;
__asm__ ("pmaxsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ unsigned long long rdtsc(void){
  unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" :
  "=A" (x));
  return x;
}

#define MIN3(a, b, c) (MIN(MIN(a,b),c))
#define MIN4(a, b, c, d) (MIN(MIN(a,b),MIN(c,d)))

static __inline__ void sort6(int * in) {
  const int A=in[0], B=in[1], C=in[2], D=in[3], E=in[4], F=in[5];

  in[0] = MIN( MIN4(A,B,C,D),MIN(E,F) );

  const int
  AB = MAX(A, B),
  AC = MAX(A, C),
  AD = MAX(A, D),
  AE = MAX(A, E),
  AF = MAX(A, F),
  BC = MAX(B, C),
  BD = MAX(B, D),
  BE = MAX(B, E),
  BF = MAX(B, F),
  CD = MAX(C, D),
  CE = MAX(C, E),
  CF = MAX(C, F),
  DE = MAX(D, E),
  DF = MAX(D, F),
  EF = MAX(E, F);

  in[1] = MIN4 (
  MIN4( AB, AC, AD, AE ),
  MIN4( AF, BC, BD, BE ),
  MIN4( BF, CD, CE, CF ),
  MIN3( DE, DF, EF)
  );

  const int
  ABC = MAX(AB,C),
  ABD = MAX(AB,D),
  ABE = MAX(AB,E),
  ABF = MAX(AB,F),
  ACD = MAX(AC,D),
  ACE = MAX(AC,E),
  ACF = MAX(AC,F),
  ADE = MAX(AD,E),
  ADF = MAX(AD,F),
  AEF = MAX(AE,F),
  BCD = MAX(BC,D),
  BCE = MAX(BC,E),
  BCF = MAX(BC,F),
  BDE = MAX(BD,E),
  BDF = MAX(BD,F),
  BEF = MAX(BE,F),
  CDE = MAX(CD,E),
  CDF = MAX(CD,F),
  CEF = MAX(CE,F),
  DEF = MAX(DE,F);

  in[2] = MIN( MIN4 (
  MIN4( ABC, ABD, ABE, ABF ),
  MIN4( ACD, ACE, ACF, ADE ),
  MIN4( ADF, AEF, BCD, BCE ),
  MIN4( BCF, BDE, BDF, BEF )),
  MIN4( CDE, CDF, CEF, DEF )
  );


  const int
  ABCD = MAX(ABC,D),
  ABCE = MAX(ABC,E),
  ABCF = MAX(ABC,F),
  ABDE = MAX(ABD,E),
  ABDF = MAX(ABD,F),
  ABEF = MAX(ABE,F),
  ACDE = MAX(ACD,E),
  ACDF = MAX(ACD,F),
  ACEF = MAX(ACE,F),
  ADEF = MAX(ADE,F),
  BCDE = MAX(BCD,E),
  BCDF = MAX(BCD,F),
  BCEF = MAX(BCE,F),
  BDEF = MAX(BDE,F),
  CDEF = MAX(CDE,F);

  in[3] = MIN4 (
  MIN4( ABCD, ABCE, ABCF, ABDE ),
  MIN4( ABDF, ABEF, ACDE, ACDF ),
  MIN4( ACEF, ADEF, BCDE, BCDF ),
  MIN3( BCEF, BDEF, CDEF )
  );

  const int
  ABCDE= MAX(ABCD,E),
  ABCDF= MAX(ABCD,F),
  ABCEF= MAX(ABCE,F),
  ABDEF= MAX(ABDE,F),
  ACDEF= MAX(ACDE,F),
  BCDEF= MAX(BCDE,F);

  in[4]= MIN (
  MIN4( ABCDE, ABCDF, ABCEF, ABDEF ),
  MIN ( ACDEF, BCDEF )
  );

  in[5] = MAX(ABCDE,F);
}

int main(int argc, char ** argv) {
  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}
  };

  unsigned long long cycles = rdtsc();
  for (int i = 0; i < 6; i++) {
    sort6(d[i]);
  }
  cycles = rdtsc() - cycles;
  printf("Time is %d\n", (unsigned)cycles);

  for (int i = 0; i < 6; i++) {
    printf("d%d : %d %d %d %d %d %d\n", i,
     d[i][0], d[i][1], d[i][2],
     d[i][3], d[i][4], d[i][5]);
  }
}

EDITAR:
Rango solución de pedido inspirada en Rex Kerr, Mucho más rápido que el lío anterior

static void sort6(int *o) {
const int 
A=o[0],B=o[1],C=o[2],D=o[3],E=o[4],F=o[5];
const unsigned char
AB = A>B, AC = A>C, AD = A>D, AE = A>E,
          BC = B>C, BD = B>D, BE = B>E,
                    CD = C>D, CE = C>E,
                              DE = D>E,
a =          AB + AC + AD + AE + (A>F),
b = 1 - AB      + BC + BD + BE + (B>F),
c = 2 - AC - BC      + CD + CE + (C>F),
d = 3 - AD - BD - CD      + DE + (D>F),
e = 4 - AE - BE - CE - DE      + (E>F);
o[a]=A; o[b]=B; o[c]=C; o[d]=D; o[e]=E;
o[15-a-b-c-d-e]=F;
}

Intente ordenar 'fusionando lista ordenada'. :) Utilice dos arreglo. El más rápido para el arreglo pequeño y grande.
Si concatenas, solo compruebas dónde insertar. Otros valores más grandes que no necesita comparar (cmp = a-b>0).
Para 4 números, puede usar el sistema 4-5 cmp (~4.6) o 3-6 cmp (~4.9). Orden de burbuja use 6 cmp (6). Un montón de cmp para números grandes código más lento.
Este código usa 5 cmp (no MSL sort):
if (cmp(arr[n][i+0],arr[n][i+1])>0) {swap(n,i+0,i+1);} if (cmp(arr[n][i+2],arr[n][i+3])>0) {swap(n,i+2,i+3);} if (cmp(arr[n][i+0],arr[n][i+2])>0) {swap(n,i+0,i+2);} if (cmp(arr[n][i+1],arr[n][i+3])>0) {swap(n,i+1,i+3);} if (cmp(arr[n][i+1],arr[n][i+2])>0) {swap(n,i+1,i+2);}

MSL principial 9 8 7 6 5 4 3 2 1 0 89 67 45 23 01 ... concat two sorted lists, list length = 1 6789 2345 01 ... concat two sorted lists, list length = 2 23456789 01 ... concat two sorted lists, list length = 4 0123456789 ... concat two sorted lists, list length = 8

Código Js

function sortListMerge_2a(cmp)	
{
var step, stepmax, tmp, a,b,c, i,j,k, m,n, cycles;
var start = 0;
var end   = arr_count;
//var str = '';
cycles = 0;
if (end>3)
	{
	stepmax = ((end - start + 1) >> 1) << 1;
	m = 1;
	n = 2;
	for (step=1;step<stepmax;step<<=1)	//bounds 1-1, 2-2, 4-4, 8-8...
		{
		a = start;
		while (a<end)
			{
			b = a + step;
			c = a + step + step;
			b = b<end ? b : end;
			c = c<end ? c : end;
			i = a;
			j = b;
			k = i;
			while (i<b && j<c)
				{
				if (cmp(arr[m][i],arr[m][j])>0)
					{arr[n][k] = arr[m][j]; j++; k++;}
				else	{arr[n][k] = arr[m][i]; i++; k++;}
				}
			while (i<b)
				{arr[n][k] = arr[m][i]; i++; k++;
}
			while (j<c)
				{arr[n][k] = arr[m][j]; j++; k++;
}
			a = c;
			}
		tmp = m; m = n; n = tmp;
		}
	return m;
	}
else
	{
	// sort 3 items
	sort10(cmp);
	return m;
	}
}

Ordenar 4 elementos con uso cmp==0. Numbers of cmp is ~4.34 (FF native have ~4.52), but take 3x time than merging lists. Pero mejor menos operaciones cmp, si tienes grandes números o texto grande. Editar: error reparado

Prueba en línea 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;
}

Tal vez yo am tarde a la fiesta, pero al menos mi contribución es un nuevo enfoque.

• El código muy debe estar en línea
• incluso si está en línea, hay demasiadas ramas
• la parte de análisis es básicamente O (N (N-1)), lo que parece correcto para N=6
• el código podría ser más eficaz si el costo de swap sería superior (irt el costo de compare)
• Confío en que las funciones estáticas estén en línea.
• El método es relacionado con rank-sort
  • en lugar de rangos, se usan los rangos (compensaciones) relativos.
  • la suma de los rangos es cero para cada ciclo en cualquier grupo de permutación.
  • en lugar de SWAP()dos elementos, los ciclos son perseguidos, necesitando solo un temp, y un swap (register->register) (new

Actualización: se cambió un poco el código, algunas personas usan compiladores C++ para compilar código C...

#include <stdio.h>

#if WANT_CHAR
typedef signed char Dif;
#else
typedef signed int Dif;
#endif

static int walksort (int *arr, int cnt);
static void countdifs (int *arr, Dif *dif, int cnt);
static void calcranks(int *arr, Dif *dif);

int wsort6(int *arr);

void do_print_a(char *msg, int *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", *arr);
        }
fprintf(stderr,"\n");
}

void do_print_d(char *msg, Dif *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", (int) *arr);
        }
fprintf(stderr,"\n");
}

static void inline countdifs (int *arr, Dif *dif, int cnt)
{
int top, bot;

for (top = 0; top < cnt; top++ ) {
        for (bot = 0; bot < top; bot++ ) {
                if (arr[top] < arr[bot]) { dif[top]--; dif[bot]++; }
                }
        }
return ;
}
        /* Copied from RexKerr ... */
static void inline calcranks(int *arr, Dif *dif){

dif[0] =     (arr[0]>arr[1])+(arr[0]>arr[2])+(arr[0]>arr[3])+(arr[0]>arr[4])+(arr[0]>arr[5]);
dif[1] = -1+ (arr[1]>=arr[0])+(arr[1]>arr[2])+(arr[1]>arr[3])+(arr[1]>arr[4])+(arr[1]>arr[5]);
dif[2] = -2+ (arr[2]>=arr[0])+(arr[2]>=arr[1])+(arr[2]>arr[3])+(arr[2]>arr[4])+(arr[2]>arr[5]);
dif[3] = -3+ (arr[3]>=arr[0])+(arr[3]>=arr[1])+(arr[3]>=arr[2])+(arr[3]>arr[4])+(arr[3]>arr[5]);
dif[4] = -4+ (arr[4]>=arr[0])+(arr[4]>=arr[1])+(arr[4]>=arr[2])+(arr[4]>=arr[3])+(arr[4]>arr[5]);
dif[5] = -(dif[0]+dif[1]+dif[2]+dif[3]+dif[4]);
}

static int walksort (int *arr, int cnt)
{
int idx, src,dst, nswap;

Dif difs[cnt];

#if WANT_REXK
calcranks(arr, difs);
#else
for (idx=0; idx < cnt; idx++) difs[idx] =0;
countdifs(arr, difs, cnt);
#endif
calcranks(arr, difs);

#define DUMP_IT 0
#if DUMP_IT
do_print_d("ISteps ", difs, cnt);
#endif

nswap = 0;
for (idx=0; idx < cnt; idx++) {
        int newval;
        int step,cyc;
        if ( !difs[idx] ) continue;
        newval = arr[idx];
        cyc = 0;
        src = idx;
        do      {
                int oldval;
                step = difs[src];
                difs[src] =0;
                dst = src + step;
                cyc += step ;
                if(dst == idx+1)idx=dst;
                oldval = arr[dst];
#if (DUMP_IT&1)
                fprintf(stderr, "[Nswap=%d] Cyc=%d Step=%2d Idx=%d  Old=%2d New=%2d #### Src=%d Dst=%d[%2d]->%2d <-- %d\n##\n"
                        , nswap, cyc, step, idx, oldval, newval
                        , src, dst, difs[dst], arr[dst]
                        , newval  );
                do_print_a("Array ", arr, cnt);
                do_print_d("Steps ", difs, cnt);
#endif

                arr[dst] = newval;
                newval = oldval;
                nswap++;
                src = dst;
                } while( cyc);
        }

return nswap;
}
/*************/
int wsort6(int *arr)
{
return walksort(arr, 6);
}

Bueno, si son solo 6 elementos y puedes aprovechar el paralelismo, quieres minimizar la ramificación condicional, etc. ¿Por qué no generas todas las combinaciones y pruebas de pedido? Me atrevería a decir que en algunas arquitecturas, puede ser bastante rápido (siempre y cuando tengas la memoria preasignada)

Aquí hay tres métodos de ordenación típicos que representan tres clases diferentes de Algoritmos de Ordenación:

Insertion Sort: Θ(n^2)

Heap Sort: Θ(n log n)

Count Sort: Θ(3n)

Pero echa un vistazo a Discusión de Stefan Nelsson sobre el algoritmo de ordenación más rápido? donde se discute una solución que se reduce a O(n log log n).. echa un vistazo a su implementación en C

Este algoritmo de clasificación semi-lineal fue presentado por un documento en 1995:

A. Andersson, T. Hagerup, S. Nilsson, and R. Raman. Ordenar en lineal tiempo? En el Procedimiento del 27º Simposio Anual de la ACM sobre la Teoría de Computing, pages 427-436, 1995.